2009/12/29 9.1.3静态树表的查找(2) 9.1.3静态树表的查找(3) PH值：定树的带权内略轻长度 次优查找树(Nearly Optimal Search Tree):若某个二又树的PH 如果只考也查找成功的情况， 值在所有具有同样权值的二又树中近似为最小，则称它为次忧查找 引入常量c,令e产p,(-12…n0,为结点的查找源率，则称为结 树。 点的权， PH=户为精银内每长度之和 次优查找树的构造 ·限个记影米速提地流能精一区，一-空限最小性 其中：m为二又树（判定前）上的结点个熏（即有序表的长虎：为 。分别对于序洲，4 一4和…构逢可操次忧查找满，并分 第：个结点在二又刺上的是次。 别设为根结赢的左子制和右子州。 ,静志最忧查找树Static Optimal Search Tree) 为便于计算△乃引入累计权值南w,=∑w,,并设4-5m4-0 一PH值取最小的二叉树， 构造静态最优责找树花费的时间代价校高1 =k--(m4-w4 =《4+w）-w-m- 25/103 26/103 圄 9.1.3静态树表的查找(4) 9.1.3静态树表的查找(5) 次优查找树的递归构造算法 例9-1(P223-224) Status SecondOptimal(BiTree &T,Elem Type Rl. fleat swl int low,int high)( 23 4 89 kev i abs(dw-swljl-sm-lmin)【 j:mi-abdw-swsm-l医 28 TBiTree)(izcof(BiTNode))exiOVERFLOW AP. 22 15 15 23 AP 1 6 9 8 7 AP AP, >rchild,B.sm,i+1,highk 271103 28/103 9.1.3静态树表的查找(6) 9.1.4索引顺序表的查找(1) 次优查找树构造算法的不足 在构造中未考察单个关健字的相应权值，则有可能出 ■分块查找（索引顺序查找） 现放选为根的关健字的权值比与它相邻的关健字的权值 小 ,查找表结构：以素引顺序表表示 调墓方法：进取邻近的权值较大的关键字作次优查找树的 ·起因 根结点。 ,顺序查找的不足：T(n)=O() 例9-2（略，P224) 。评价 :折半查找：T(n)=0(Iog2n),但要求查找表必须 ·大重实验表男，改优查找树和最代查找满的查找性能仅为 是有序表 12%,覆少超过3% 。基本思想：分块有序，索引表是有序表，索引 。构造次优查找满的算法的时间复杂度为0(logn) 次优查找树的查找过置类似于折半查找 项是（最大关键字，指针项） 29/108 合 30/103 圄 52009/12/29 5 9.1.3 静态树表的查找(2)  PH值：判定树的带权内路径长度 如果只考虑查找成功的情况， 引入常量 c，令wi =cpi (i=1,2,…,n),(pi 为结点的查找概率)，则称wi 为结 点的权 称 25/103 ， 为带权内路径长度之和。 其中：n 为二叉树（判定树）上的结点个数(即有序表的长度)；hi 为 第 i 个结点在二叉树上的层次。  静态最优查找树(Static Optimal Search Tree) ——PH值取最小的二叉树． 构造静态最优查找树花费的时间代价较高！ 1 n i i i PH w h    9.1.3 静态树表的查找(3)  次优查找树(Nearly Optimal Search Tree)：若某个二叉树的PH 值在所有具有同样权值的二叉树中近似为最小，则称它为次优查找 树。 次优查找树的构造 26/103   取第i个记录ri 构造根结点，使得 取最小值 (l≤i ≤h)  分别对子序列{rl , rl+1 , …, ri-1}和{ri+1 , …, rh}构造两棵次优查找树，并分 别设为根结点ri 的左子树和右子树． 为便于计算 ，引入累计权值和 ，并设wl-1 = swl-1 =0 1 1 h i i jj ji jl P w w        P i i j j l sw w   1 1 1 1 ( )( ) ( ) i hi i l hl ii P sw sw sw sw sw sw sw sw            9.1.3 静态树表的查找(4)  次优查找树的递归构造算法 Status SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high) { i=low; min = abs(sw[high]-sw[low]); dw = sw[high]+sw[low-1]; f (j l 1 j hi h j) 27/103 for (j=low+1; j<=high; ++j) if(abs(dw-sw[j]-sw[j-1])<min) { i=j; min=abs(dw-sw[j]-sw[j-1]); } if ( !(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = R[i]; if (i==low) T->lchild = NULL; else SecondOptimal(T->lchild, R, sw, low, i-1); if (i==high) T->rchild = NULL; else SecondOptimal(T->rchild, R, sw, i+1, high); return OK; } 9.1.3 静态树表的查找(5)  例9-1 (P223-224) j0123456789 keyj ABCDE FGH I 28/103 wj 0112534435 swj 0 1 2 4 9 12 16 20 23 28 ΔPj 27 25 22 15 7 0 8 15 23 ΔPj 11 9 6 1 9 8 1 7 ΔPj 312 0 0 0 ΔPj 0 0 9.1.3 静态树表的查找(6)  次优查找树构造算法的不足 在构造中未考察单个关键字的相应权值，则有可能出 现被选为根的关键字的权值比与它相邻的关键字的权值 小． 29/103 调整方法：选取邻近的权值较大的关键字作次优查找树的 根结点． 例9-2 (略，P224)  评价  大量实验表明，次优查找树和最优查找树的查找性能仅为 1%~2%，很少超过3%  构造次优查找树的算法的时间复杂度为O(nlogn)  次优查找树的查找过程类似于折半查找 9.1.4 索引顺序表的查找(1)  分块查找(索引顺序查找)  查找表结构：以索引顺序表表示 起因 30/103   顺序查找的不足：T(n) = O(n)  折半查找：T(n) = O(log2n)，但要求查找表必须 是有序表  基本思想：分块有序，索引表是有序表，索引 项是(最大关键字, 指针项)