第五章 查找算法课件

1、3.4 3.4 查找查找查找算法大致包括： 顺序查找 二分(折半查找) B树 散列（Hash法） 查找中间值顺序查找顺序查找 对于无序的序列，只能进行顺序查找。从起点开始往下查，直到找到了正确的键为止，然后停止。 算法：从ai (i=0,1,ai (i=0,1,N-1),N-1)中查找x x： for(i=0;iN;i+)for(i=0;iN;i+) if (x=ai) break; if (x=ai) break; return i; /if iN then found else not found return i; /if iN then found else not found 改进1

2、：在结尾处加一个虚拟记录，减少一测试条件 aN=x;aN=x; while (1) while (1) if (x!=ai) if (x!=ai) i+; i+; else else break; break; return i; return i; 改进2： 复杂度分析： 如果每个输入键都以相同概率出现，则在一次成功查找中平均比较次数为： 方差： 即： （标准差） 21.321NNN) 1(121) 1(211)21(12212212NNiNNiNNiNiNN289. 012 改进3： 如果键为递增次序，查找失败可更快给出 i=0; aN=x+1;i=0; aN=x+1; while (1)

3、 while (1) if (x=ai) if (x=ai) break; break; else else i+; i+; if (x=ai) if (x=ai) return i; return i; else else return N; return N;二分二分( (折半折半) )查找查找 每次查找决定下一次查找该在哪一半。 算法：给定有序序列ai (i=0,.,N-1)，查找x l=0;u=N-1; while (1) if(ul) return N; /未找到 else i=(l+u)/2; if(x=ai) /找到 return i; else if(xai) if(xai)

4、u=i-1; u=i-1; else else l=i+1; l=i+1; 定理： 如果 ，则上面算法进行一个成功查找需要作(min l,max k)(min l,max k)次比较。 如果 ，则一个不成功的查找需要k k次比较 如果 ,则一个不成功的查找需要k-1k-1次或k k次比较。复杂度：O(logN)kkN22112 kN1221kkN二叉树二叉树有序表存放结构线性表：插入/删除困难移动 静态链表： 动态树：插入/删除容易 动态 二叉树二叉树：叶片是一个码，叶片到根的长度就是该码长度。频率频率：码出现频率高时应当短一些。问题：问题：假定k个码出现频率分别为p1，p2，.，pk，并且二

5、叉树T对应的码长为lj，对应查找长度为 。则Huffman树满足：11kiipkjjjlpTm1)()(min)(TmTmH Huffman Huffman 树树引理：引理：HuffmanHuffman树无只有一个儿子的内点。树无只有一个儿子的内点。 将该内点消去后，所得m(T)会减少，与其为Huffman树矛盾。 假定 为p1+p2,p3, ,pk对应最佳二叉树，T为p1,p2,p3,. .,pk, ：将p1，p2对应叶消去，赋以p1p2 ,则有: ,并且 。 再加一层 ：将 叶片p1p2变成两个叶片p1，p2，则 于是： 即： 从而：kpppp.321_T_T)()(_TmTm21_)()

6、(ppTmTm_T21_)()()(ppTmTmTm21_21_)()(ppTmppTm)()(_TmTm)()(_TmTm_T例： m(T)=2*0.2+1*0.5+4*0.1+4*0.05+3*0.15=1.95 用等长编码时，必须有三位。 p1 p2 p3 p4 p5 0.2 0.5 0.1 0.05 0.15 00 1 0101 0100 01120101105143011.00.5050.20.30.150.150.050.10 设x1,x2 ,xn的查找频率分别为p1,p2,pn，由 而出现失败的概率为q0,q1, q2,qn，则有： 将序列x1,x2,x3,xn用二叉树T表示：n

7、个内点对应x1,xn，n+1个叶子对应n+1种失败状态y0,y1,yn。点xi到树根距离l(xi)，从根xi到比较次数为l(xi)+1；从根到l(yi)须作l(yi)次比较。定义T的带权路径长度：最佳二叉树是使C(T)极小的二叉树。101niiniiqpniiiniiiylqpxlTC01)() 1)()(3.4.3.2 3.4.3.2 最佳二分法最佳二分法nnnxzxzxxzxxz,.,1211 内径长度：树的所有内点到树根的路径长度之和：I(T) 外径长度：树的所有叶子到树根的路径长度之和：E(T) 对于有n个内点的二分树： I(T)=I(Tl)+I(Tr)+(n-1) E(T)=E(Tl

8、)+E(Tr)+n 并且： E(T)=I(T)+2nXkTlTr例：n=4, x1x2x3x4 ，(p1,p2,p3,p4)=( , ， ， ) (q0,q1,q2,q3,q4)=( , , , , )，则最佳树为： C(T)= 1（ ） 3( + + )2+( ) =2163163162161162162161161161x2x1x3x416316316221611621621611611613x2x1x3x4u0u1u2u3u4方差:1672 比较：线性形状树x1x2x3x425. 2491636) 41614161316121621162() 4161316221631163()(TC方

9、差:1875.12均衡二叉树均衡二叉树AVLAVL定义：设Tl和Tr分别是二叉树T的左右两个子树，则满足下列条件的二叉树称为高度均衡二叉树： （1） ，其中代表树T的高度。 （2） Tl和Tr亦为高度均衡二叉树。1)()(rlThTh 最坏情况下高度： 高度为h的二叉树Th， 左边高度为h-1的左子树Th-1， 右边高度为h-2的右子树Th-2，并且递归生成！ Th-1Th 2h-2hh-1设高度为h的高度均衡二叉树节点数为bh，则:令 ，则： 其中： 当1和h相当大时：从而 或2111021,bbbbbhhh.)(2210 xbxbbxG)1.()()(51)(222 xxxG251 251

10、1)52321()52321(1151)(5111221212 hhhhhhhbhhhb)251(89. 1)52321(1hbhln784972. 4hbh2log4404.1平均查找时间：设 是高度为h的均衡树所有的点查找所需比较次数的总和，即所有内点到树根的距离加1的总和。令从而近似有：ha3, 11021aabaaahhhhhhhbac hhhhhhhhhhhhbbbbbabbbaba2221112211)251(,)251(,)251(89.1hhhhhhbbbbb2/3, 11)251()251(102211ccccchhh令，则其中故：当h充分大时 即平均查找时间较完全均衡树多0

11、.042倍。 均衡二叉树的插入和消去 2210)(xcxccxG0112212)(211)1 (2)(kkkkxddxxxxxxG) 1(51)(5111011kkkjjjjkkd)(2(5251) 12(521)(211121hhhhhhddchhhbhbhc22log4404. 1,log042. 17236. 03.4.5 3.4.5 散散 列列散列，杂凑，或Hash法将关键字通过映射h映射到地址上，该映射称为散列函数 散列函数散列函数 I.除法 II.乘法 其中GCD（A,W）=1， AW。 另有如平方中间法，折叠法等（折叠法：除最后一部分外分成位数相等几部分，直接作和或变形作和求得）

12、Mkkhmod)(1mod)(kWAMkh避免冲突 冲突： ，但 解决方法： (1)链地址法 (2)开放地址法：运用一系列散列函数，直至为空 线性探测 ：找下一个空的 二次探测 (3)多重散列（Rehashing）21kk )()(21khkh定理:令 为使用一均匀散列函数时散列表的装入密度， UN为对不在表中关键字比较次数的期望，SN为在表中关键字比较次数的期望，则:(i) 对线性开地址法 (ii) 对重散列，随机探测法和二次探测法(iii) 对链地址法MN /211121NU11121NS11NU1ln1NSeUN21NS假定散列函数是均匀的，可能的关键字分布是均匀的，表的大小为M，假定已

13、插入k个关键字，现插入第k+1个关键字，则第i次成功的概率为：则插入第k+1个关键字次数期望值为：MkMMkp/111/2MkMMkp1222211iMkMiMikMkMkMkpi111221111111kMMiMkMiMikMkMkiipEkikiik 注意：插入时探测次数（probe）恰巧是查找时探测次数。令表的大小为M，表中含有m个关键字，则平均查找次数：其中： ，为调和函数 ， 0.577216令：111112111mMMmkmkkHHmMkMMmEmEnHn131211 nHnln)1/(Mm1ln11ln11ln1ln1mMMmMME 假定诸键所占表中位置是随机的，使得k个已占用，

14、Mk个空的 种配置是等可能的（表中每个单元占用同其他单元无关），则插入第k1个关键字需i次探测的概率，是i1个单元已占用，和另一个单元是空的配置数，除以总配置数kMkMkMiMpi11111111111111111111111111kMMkMMkMMkMkMkMMkMkMMkMMkMkMiMkMMkMkMiMiMMkMkMiMiipEkikikikiik查找中间查找中间1“快速”查找 基于快速分类的思想，有下面的快速查找 查找S中第k个大小的元素（标号从1开始） QuickSelect(S,k) Step1:在S中随机选择一x（均匀分布） Step2:令 及 Step3:返回：:1xySyS:

15、2xySySotherwisexkSSifSkStQuickSeleckSifkStQuickSelec|) 1|,(|),(21211假定T(n)为在S中找到第k个元素所需的期望时间，并假定|S|=n，由于x为任意选定，选到第i个的概率为 。从而而额外时间为于是猜测一个结果：线性的代入上式：n1njjijitimeExtraEnnT1Pr|1)(nikifiTkiifkiifinTtimeExtraE1) 1(011)(111) 1(1)(11)(kinkiiTninTnnnTcnnT)(111) 1()(1)(kinkiincinncnnT即对内部求和：上式中当 时有极大值。从而，只需 即

16、可使 成立。定理：定理：当均匀选择时，QuickSelect的平均比较次数的期望至多为4n。111)1()(1)(kinkiiinncnnT43)22(21)3222(21)1)()1(1)(1(21) 1()(22222111nknknnkknknnkknknnkiinnkiki2nk )431 (431)(2cnnncnnT4ccnnT)(2一个改进的算法 欲使算法比较次数减少，应当使得x离查找项尽可能近。 实际中，选择三个数y，z，w，而将其中值做为x。 进一步：取 个随机元素R，令x为R的中值。再根据x对S进行划分，即构造 及 中间值应用该算法时需要平均 次比较。43nr :1xySy

17、S:2xySyS)(5 . 1non 3线性时间的确定算法 关键：找到离中值尽可能近的划分元素。算法思路假定n=5m,将n个元素划分为m个组，每组有5个元素；找到每组中的中值；再找到m个中值的中值，记为x00 x？注意：上图的纵向为5元组，横向为m个子组； 其中红色部分大于或等于；而绿部分小于或等于；只需 对其中与大小未知部分进行比较。算法：F(S,k)：寻找集合S中的第k个元素。假定|S|=n,并且n=5m。Step1:将集合S划分成5个元素为一组的小组；Step2:令S1为这些组的中值，这里|S1|=mStep3:x0=F(S1,m/2)Step4:令 及 。 如果|S2|k，则F(S2,k)； 如果|S3|n-k+1 ，则F(S3,k+|S3|-n)； 否则，返回。,|02xxSxxS,|03xxSxxS复杂度分析：最坏情况 令M(n)为从n个元素中找到第k个元素的比较次数。 从5个元素中找到中值需要7次比较； 第二项为找到x0所需要进行的比较次数； 第三项为完成其余部分的划分进行的比较次数； 最后一项为从S2或S3继续查找的时间。 由于S2和S3都至少占到个 元素（至少一半！），从而，需要查找的元素不会超过|)| |,(|()10/4()5/()5()5