数据结构：第8章 查找

《数据结构：第8章 查找》由会员分享，可在线阅读，更多相关《数据结构：第8章 查找（148页珍藏版）》请在金锄头文库上搜索。

1、1数据结构国家精品课程2024/7/31第八章第八章 查查 找找2数据结构国家精品课程2024/7/31l查找查找-即在某种数据结构中找出满足条件的结点。即在某种数据结构中找出满足条件的结点。l查找表查找表：是由同一类型的数据元素构成的集合。是由同一类型的数据元素构成的集合。l查找结果：成功、失败。查找结果：成功、失败。l平均查找长度平均查找长度查找一个结点所作的平均比较次查找一个结点所作的平均比较次数（衡量一个查找算法优劣的主要标准）。数（衡量一个查找算法优劣的主要标准）。3数据结构国家精品课程2024/7/31查找算法的查找算法的四个特征四个特征：内外有别内外有别：分为内查找和外查找。：分

2、为内查找和外查找。静静态态动动态态：静静态态查查找找时时，表表的的内内容容不不变变；动动态态查查找找时时，表中的内容不断地变化。表中的内容不断地变化。原原词词变变词词：原原词词系系指指用用原原来来的的关关键键词词，变变词词系系指指使使用用经经过变换的关键词。过变换的关键词。数字文字数字文字：指进行比较的时候，是否用数字的性质。：指进行比较的时候，是否用数字的性质。4数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契

3、查找斐波那契查找8.2.4插值查找插值查找二、树形结构的查找二、树形结构的查找三、散列三、散列5数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找8.1.1无序表的顺序查找无序表的顺序查找l现现实实生生活活中中顺顺序序查查找找的的例例子子很很多多。比比如如，在在一一个个班班级级的的名名册册中中查查找找某某个个学学生生的的名名字字。通通常常的的做做法法是是，顺顺序序比比较较名名册册中的每个名字。这就是顺序查找中的每个名字。这就是顺序查找。l顺顺序序查查找找的的基基本本思思想想：从从线线性性表表的的起起始始结结点点开开始始，逐逐个个检检查查每每个个结结点点，或或者者找找到到关关

4、键键词词Ki=K，或或者者以以in(i为为表表中中记录的下标，记录的下标，n为线性表的元素个数为线性表的元素个数)查找失败告终。查找失败告终。l顺顺序序查查找找很很简简单单、明明显显，该该方方法法是是讨讨论论查查找找问问题题的的一一个个有有用用的的起起点点，因因为为许许多多错错综综复复杂杂的的查查找找算算法法都都是是以以它它为为基基础础的的。6数据结构国家精品课程2024/7/31算算法法S(N，R，K.i)/*给给定定包包含含N个个记记录录R1，R2，RN，其其对对应应的的关关键键词词分分别别为为K1，K2，KN的的一一个个表表，S查查找找一一个个给定的变元给定的变元K.这里假定这里假定N

5、1.*/S1.初始化初始化置置i1.S2.比较关键词比较关键词如果如果K Ki，则算法成功结束，则算法成功结束.S3.推进推进i置置ii 1.S4.i N?若若i N，则则返返回回步步骤骤S2；否否则则此此算算法法以以查查找找失失败败告告终终.7数据结构国家精品课程2024/7/31算法算法S(N，R，K.i)/*给给定定包包含含N个个记记录录R1，R2，RN，其其对对应应的的关关键键词词分分别别为为K1，K2，KN的的一一个个表表，S查查找找一一个个给给定定的的变变元元K.这里假定这里假定N 1.*/S1初始化初始化i1S2比较关键词比较关键词WHILE(i N)&(KKi)DOii+1.

6、8数据结构国家精品课程2024/7/31在表中引入一个在表中引入一个“虚拟虚拟”记录记录RN 1，能提高算法，能提高算法S的效率。的效率。算法算法Q(N，R，K.i)/*算算法法Q与与S基基本本相相同同，区区别别在在于于Q之之表表（或或文文件件）的的末末尾添加了一个尾添加了一个“虚拟虚拟”记录记录RN 1.*/Q1.初始化初始化置置i1，并置，并置KN 1K .Q2.比较关键词比较关键词如果如果K Ki，则转到步骤，则转到步骤Q4.Q3.推进推进i 置置ii 1，并返回步骤，并返回步骤Q2.Q4.i N?如果如果i N，则算法成功结束；，则算法成功结束；否则以查找失败告终否则以查找失败告终./

7、此时有此时有i N 19数据结构国家精品课程2024/7/31算法算法Q（N，R，Ki）/* 给给定定记记录录R1，R2，RN的的表表，其其中中Ri的的关关键键词词为为Ki （1iN），本算法查找关键词等于），本算法查找关键词等于K的记录的记录*/Q1初始化初始化 i1KN+1KQ2比较关键词比较关键词WHILEKKiDOii+1.从从算算法法S到到算算法法Q利利用用了了一一个个重重要要的的“加加速速原原理理”:当当算算法法的的一一个个内内循循环环要要测测试试两两个个或或多多个个条条件件时时，应应力力图图将将其其减减少少成成一一个条件。个条件。算法算法Q大约比算法大约比算法S节省百分之二十的运

8、行时间。节省百分之二十的运行时间。10数据结构国家精品课程2024/7/31 查找查找成功成功的平均查找长度：的平均查找长度：查找查找失败失败的查找长度：的查找长度：N+1顺序查找的时间复杂度：顺序查找的时间复杂度：O(N)11数据结构国家精品课程2024/7/31算法算法Q (N，R，K.i)Q 1.初始化初始化置置i 1. KN 1K.Q 2.前进两步前进两步置置i i 2.Q 3.Ki :K若若Ki K，则转到步骤，则转到步骤Q 5.Q 4.Ki 1:K若若Ki 1 K，则返回步骤，则返回步骤Q 2；否则置否则置ii 1./查找成功，其位置为查找成功，其位置为i 1Q 5.i N?若若i

9、 N，则算法成功结束；否则算法以查找失，则算法成功结束；否则算法以查找失败告终败告终./此时此时i N 1算法算法Q还能更快吗？还能更快吗？将算法将算法Q中中i的增量由的增量由1变成变成2，推进，推进i之操作减少将近一半。之操作减少将近一半。算法算法Q 的运行时间比算法的运行时间比算法S减少了约百分之三十。减少了约百分之三十。12数据结构国家精品课程2024/7/31l算算法法S、算算法法Q、算算法法Q 说说明明：提提高高一一个个算算法法（或或程序）之效率很可能有很大潜力。程序）之效率很可能有很大潜力。l顺序查找优缺点顺序查找优缺点:优点优点:算法简单，且适用面广。算法简单，且适用面广。缺点缺

10、点:平均查找长度较大，平均查找长度较大，N很大时很大时查找效率低查找效率低。13数据结构国家精品课程2024/7/31自组织表自组织表l表中各元素被查找的概率并不一定相同。把经常出现的表中各元素被查找的概率并不一定相同。把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组经常出现的元素自动向表的后端移动，并称以该方式组织的表为织的表为自组织表自组织表。vMOVE-AHEAD-ONEvMOVE-TO-FRONT14数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找8.1.1

11、无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找15数据结构国家精品课程2024/7/318.1.2有序表的顺序查找有序表的顺序查找算法算法T（R，n，Ki）/*表表R1，R2，Rn按照关键词递增有序按照关键词递增有序*/T1初始化初始化i1Kn+1+.T2顺序与表中各元素比较顺序与表中各元素比较WHILEKKiDOii+1.T3若未找到，设若未找到，设in+1IFKKiTHENin+1.16数据结构国家精品课程2024/7/31l算法成功结束时算法

12、成功结束时1in，否则，否则i=n+1l与与算算法法Q相相比比较较，对对于于成成功功的的查查找找，算算法法T的的期期望望复复杂杂性性为为(n+1)/2，与与算算法法Q的的期期望望复复杂杂性性相相同同；而而对对于于不不成成功功的的查查找找算算法法T的的期期望望复复杂杂性性为为(n+1)/2，而而算算法法Q为为n+1，算算法法T比比算算法法Q大约快一倍。大约快一倍。l先先将将文文件件排排序序，再再查查找找，是是一一个个快快速速的的查查找找方方法法。但但如如果果只只需需对对表表查查找找一一次次，则则进进行行顺顺序序查查找找比比对对这这个个表表进进行行完完整整排排序序要要快快；如如果果要要在在同同一一

13、个个文文件件中中不不断断进进行行查查找找，那那么么将将表表按按序序排列再查找是个很好的方法。排列再查找是个很好的方法。17数据结构国家精品课程2024/7/31l有有序序表表（K1 K2 KN）的的查查找找，比比较较K和和Ki后后，有有:K Ki，不必考虑子表不必考虑子表Ri，Ri 1，RNK Ki，查找成功结束查找成功结束K Ki ，不必考虑子表不必考虑子表R1，R2，Ri l使用不同的规则确定使用不同的规则确定i，可得到不同的查找方法。，可得到不同的查找方法。l算算法法T的的改改进进方方法法：对对半半查查找找、一一致致对对半半查查找找、斐斐波那契查找和插值查找等。波那契查找和插值查找等。1

14、8数据结构国家精品课程2024/7/318.1线性表的查找线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找19数据结构国家精品课程2024/7/318.2.1对半（折半，二分）查找对半（折半，二分）查找1、算法思想：、算法思想：K与与待待查查表表中中间间记记录录的的关关键键词词K N/2 比比较较，其其结结果果有有三三：KK N/2 ，K=K N/2 ，KK N/2 由由情情况况知知查查找找成成功功结结束束，由由情情况况和和能能

15、确确定定下下一一次次应应到到表表的的哪哪一一半半中中去去查查找找，即即将将查查找找范范围围缩缩小小一一半半；并并对对确确定定的的那那一一半半重重复复上上述述过过程程，直直至至找找到到所所查查记记录录或或确确定该记录不在表中。定该记录不在表中。例例假定有序表假定有序表A中中10个元素的关键词序列：个元素的关键词序列：12，23，26，37，54，60，68，75，82，96当给定值分别为当给定值分别为96和和58时进行二分查找。时进行二分查找。20数据结构国家精品课程2024/7/312、对半查找算法描述、对半查找算法描述算法算法B(N，R，K.i)/*给定关键词在递增次序下（即给定关键词在递增

16、次序下（即K1 K2 KN）包含）包含N个记个记录录R1,R2,RN 的表，查找给定变元的表，查找给定变元K.用两个指针用两个指针s和和e分别分别指向当前被查找文件之最左边和最右边记录的下标。指向当前被查找文件之最左边和最右边记录的下标。*/B1.初始化初始化置置s 1.e N.B2.取中点取中点如果如果e s，则该算法以失败告终；否则，置，则该算法以失败告终；否则，置i (s +e)/2 。B3.比较比较如果如果K Ki，则转步骤，则转步骤B5；如果如果K =Ki，则算法成功结束。，则算法成功结束。B4.调整调整e置置e i 1，并返回，并返回B2.B5.调整调整s置置s i 1，并返回，并

17、返回B2.21数据结构国家精品课程2024/7/31查找查找k=96时二分查找过程时二分查找过程(4次比较成功）次比较成功） 1234567891012 23 26 37 54 60 68 75 82 9612 23 26 37 54 60 68 75 82 96s s=1=1e e=10=10e=10e=1012 23 26 37 12 23 26 37 54 54 60 68 75 82 96 60 68 75 82 96s s=1=1i i=5=5e=10e=1012 23 26 37 54 60 68 12 23 26 37 54 60 68 7575 82 96 82 96s=6s=

18、6i=8i=812 23 26 37 54 60 68 7512 23 26 37 54 60 68 75 82 82 9696s=e=10s=e=10i=10i=10e=10e=1012 23 26 37 54 60 68 7512 23 26 37 54 60 68 75 82 82 96 96s=9s=9i=9i=922数据结构国家精品课程2024/7/31查找查找k=58时二分查找过程时二分查找过程(3次比较失败）次比较失败） 1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 1012 23 26 37 54 60 68 75 82 9612 23 26 37

19、 54 60 68 75 82 96e=10e=1012 23 26 37 12 23 26 37 5454 60 68 75 82 96 60 68 75 82 96s=1s=1i=5i=5e=10e=1012 23 26 37 54 60 68 12 23 26 37 54 60 68 7575 82 96 82 96s=6s=6i=8i=812 23 26 37 54 60 68 75 82 9612 23 26 37 54 60 68 75 82 96s=6s=6s=6s=6e=5e=5e=5e=512 23 26 37 54 12 23 26 37 54 6060 68 75 82

20、96 68 75 82 96s=6s=6e=7e=7i=6i=623数据结构国家精品课程2024/7/313、对半查找算法分析、对半查找算法分析每个圆圈结点表示关键词比较每个圆圈结点表示关键词比较K:Ki4528136971054758296231226603768=24数据结构国家精品课程2024/7/31二叉判定树二叉判定树二叉判定树，二叉判定树，T（s，e）的）的递归定义递归定义如下：如下：(1)当当e-s+1 0时，时，T（s，e）为空树；）为空树；(2)当当e-s+10时时，二二叉叉判判定定树树的的根根结结点点是是有有序序表表中中序序号号为为 (e+s)/2 的的记记录录，根根结结点

21、点的的左左子子树树是是与与有有序序表表Rs，Rs+1，R (e+s)/2 -1相相对对应应的的二二叉叉判判定定树树，根根结结点点的的右右子子树树是是与与有有序序表表R (e+s)/2 +1，R (e+s)/2 +2，Re相对应的二叉判定树。相对应的二叉判定树。25数据结构国家精品课程2024/7/31T（1，10）的二叉判定树：搜索）的二叉判定树：搜索K=96452813697105475829623122660376826数据结构国家精品课程2024/7/314528136971054758296231226603768T（1，10）的二叉判定树：搜索）的二叉判定树：搜索K=5827数据结构

22、国家精品课程2024/7/31T(1,10)查找成功查找成功的平均查找长度的平均查找长度4528136971054758296231226603768ASLSUCC(1*1+2*2+3*4+4*3)/1029/102.928数据结构国家精品课程2024/7/31查找查找失败失败的平均查找长度：的平均查找长度： ASLUNSUCCEn/(n+1)(3*5+4*6)/1139/11452813697105475829623122660376829数据结构国家精品课程2024/7/31引引理理8.1设设算算法法B对对N个个记记录录的的成成功功查查找找是是等等概概率率的的，且且对对不不成成功功的的查查

23、找找也也是是等等概概率率的的，则则成成功功查查找找的的关关键键词词比比较较的的平平均均次次数数SN=1+IN/N，不不成成功功查查找找的的关关键键词词比比较较的的平平均均次次数数UN=EN /(N+1)，其中，其中IN，EN为为T（1,N）的内、外通路长度）的内、外通路长度.引理引理8.2对半查找二叉判定树对半查找二叉判定树T（s, e）的高度是）的高度是 log2(e-s+2) .引引理理8.3设设T(1,N)是是N个个内内结结点点的的二二叉叉判判定定树树，不不考考虑虑外外结结点点T(1,N)之高度为之高度为k，T(1,N)之外结点均属于之外结点均属于k或或k 1层层.定理定理8.1算法算法

24、B在最坏情况下的关键词比较次数为在最坏情况下的关键词比较次数为 log2(N1) ，且期望复杂性等于，且期望复杂性等于O(log2N).30数据结构国家精品课程2024/7/314、二分查找总结、二分查找总结:优点优点:查找效率为查找效率为O(log2N)/比顺序查找高比顺序查找高缺点缺点:只适用于只适用于有序表有序表，且，且限于顺序存储结构，限于顺序存储结构，对线性链表无法对线性链表无法进行二分查找。进行二分查找。31数据结构国家精品课程2024/7/318.1线性表的查找线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查

25、找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找32数据结构国家精品课程2024/7/31当当N=10时一株时一株“一致一致”的二叉判定的二叉判定树树58002122434656878813792109 10 1 3 18.2.2一致对半查找一致对半查找 将对半查找的指针数量由三个将对半查找的指针数量由三个(s，i和和e )减少为两个。减少为两个。 i= N/2 ，m= N /2 =5i=i+/- m/2 ，m= m /2 =2i=i+/- m/2 ，m= m /2 =1i=i+/- m/2 ，m= 033数据结构国家精品课程2024/7/31一

26、致对半查找算法一致对半查找算法 算法算法U(N，R，K.i)/*给定包含给定包含N个记录个记录R1，R2，RN，其诸关键词满足，其诸关键词满足K1 K2 KN的一张表，本算法查找变元的一张表，本算法查找变元K.若若N为偶数，则算法有时将涉及为偶数，则算法有时将涉及一个虚拟关键词一个虚拟关键词K0，K0被置成被置成 （或小于（或小于K的任意值）的任意值）.我们假定我们假定N 1.*/U1.初始化初始化置置i N/2 ，m N/2 .U2.比比较较若若K Ki，转到，转到U3；若；若K Ki，转到，转到U4；若；若K Ki，则，则算法成功结束。算法成功结束。U3.减小减小i 若若m 0，则算法以失

27、败告终；否则置，则算法以失败告终；否则置ii m/2 ；然后置然后置m m/2 并返回并返回U2.U4.增大增大i 若若m=0，则算法以失败告终；否则置，则算法以失败告终；否则置i i m/2 ；然后置然后置m m/2 并返回并返回U2.34数据结构国家精品课程2024/7/31l算算法法U之之所所以以被被称称为为是是一一致致的的，是是因因为为，在在层层l上上的的一一个个结结点点的的编编号号与与在在层层l-1上上其其父父结结点点的的编编号号之之差差的的绝绝对对值值，对对于于层层l上上的的所所有有结结点点均均有有一一致致的的常常数数.例例如如，上上图图中中，对对第第1层层均均有有一一致致的的 3

28、，对对第第2层层均均有有一一致的致的 1，对第，对第3层均有一致的层均有一致的 1.l当当查查找找失失败败时时，U可可能能在在结结束束前前作作一一次次冗冗余余的的比比较较，如图中阴影结点所示。如图中阴影结点所示。35数据结构国家精品课程2024/7/31在算法在算法U中，每次用来找中点中，每次用来找中点i的的m 的序列如下：的序列如下：中点中点i序列如下：序列如下：于是算法于是算法U又可以改进：在运行期间，不去计算又可以改进：在运行期间，不去计算m及及i值，值，而是使用一张辅助表：而是使用一张辅助表：36数据结构国家精品课程2024/7/31算法算法C(N，R，K.i)/*算法算法C与算法与算

29、法U相似，但它使用一个辅助表来代替涉及相似，但它使用一个辅助表来代替涉及m 的计算。这个表中的项是的计算。这个表中的项是*/C1.初始化初始化置置iDELTA1.j 2.C2.比较比较若若K Ki ,则转则转C3；若；若K K i ,则转则转C4；若；若K K i ，则算法成功结束，则算法成功结束.C3.减小减小i 若若DELTAj 0，则算法以失败告终；否则，则算法以失败告终；否则置置ii DELTAj .j j 1，并转，并转C2.C4.增大增大i 若若DELTAj 0，则此算法以失败告终；否，则此算法以失败告终；否则，置则，置ii DELTAj .jj 1，并转，并转C237数据结构国家

30、精品课程2024/7/31一致对半查找算法一致对半查找算法(算法算法C)的时间复杂度分析：的时间复杂度分析：n成成功功的的查查找找：算算法法C对对应应的的二二叉叉判判定定树树与与算算法法B对对应应的的二二叉叉判判定定树树有有相相同同的的内内路路径径长长，所所以以平平均均比比较较次次数数与算法与算法B一样。一样。n不不成成功功的的查查找找：算算法法C总总是是恰恰好好进进行行 log2N +1次次比比较，比算法较，比算法B的的 log2(N1) 比较次数多比较次数多。n算算法法C中中的的算算术术运运算算仅仅包包含含加加减减法法，且且在在算算法法运运行行期期间间未未计计算算诸诸m之之值值，而而是是用

31、用一一张张辅辅助助表表来来代代替替，从从而而明明显显提提高高了了速速度度。算算法法C的的时时间间花花费费不不足足算算法法B的二分之一的二分之一。 38数据结构国家精品课程2024/7/31除了对除了对“待查表待查表”进行均匀划分之外，我们还有没进行均匀划分之外，我们还有没有新的划分思路？就是说一定要对半划分吗？对半有新的划分思路？就是说一定要对半划分吗？对半划分是最好的划分吗？划分是最好的划分吗？回答是肯定的，确实存在对半划分的替代方案回答是肯定的，确实存在对半划分的替代方案斐波那契划分。斐波那契划分。这一替代方案是更可取的，因为它只包含加、减法，这一替代方案是更可取的，因为它只包含加、减法，

32、连除以连除以2的除法都没有的除法都没有。39数据结构国家精品课程2024/7/318.1线性表的查找线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找40数据结构国家精品课程2024/7/318.2.3斐波那契查找斐波那契查找Fibonacci序列：序列：0，1，1，2，3，5，8，13，21，34，F0=0，F1=1，Fj=Fj-1+Fj-2，j2斐波那契（斐波那契（Fibonacci）查找）查找对对半半查查找找的的替替代代，以

33、以Fibonacci序序列列的的分分划划代代替替了了对半查找的均匀分划对半查找的均匀分划。41数据结构国家精品课程2024/7/31假假设设有有一一个个长长度度为为Fk+1 1的的文文件件，其其记记录录下下标标1，Fk+1 1。记记录录F k 将文件分为三个部分：将文件分为三个部分：左子文件左子文件1，Fk 1；F k；右子文件右子文件Fk+1，Fk+1 1；其其中中，左左、右右子子文文件件的的大大小小分分别别为为Fk 1，Fk 1 1，故故左左、右右子子文件还可继续进行上面的划分（文件还可继续进行上面的划分（黄金分割黄金分割）过程。）过程。42数据结构国家精品课程2024/7/31k 阶斐波

34、那契树阶斐波那契树T k 的递归定义如下：的递归定义如下：当当k 0,1时，时，T k 为空树；为空树；当当k 1时时，二二叉叉判判定定树树之之根根是是有有序序表表中中序序号号为为f k的的记记录录，根结点的左子树是与有序表根结点的左子树是与有序表k 阶斐波那契树有阶斐波那契树有fk+1 1个内结点和个内结点和fk+1个外结点个外结点.对应的二叉判定树，根为对应的二叉判定树，根为fk 1；根结点的右子树是与有序表根结点的右子树是与有序表对应的二叉判定树，是对应的二叉判定树，是k 2阶且所有结点之编号都阶且所有结点之编号都增加增加fk的斐波那契树的斐波那契树Tk 2 fk ,其根为其根为fk+f

35、k 2. 43数据结构国家精品课程2024/7/31f2T1T0+f2101f3T2T1+f321012二阶斐波二阶斐波那契树那契树T2三阶斐波三阶斐波那契树那契树T3Fibonacci序列：序列：0，1，1，2，3，5，8，13，21，34，44数据结构国家精品课程2024/7/31f4T3T2+f4210123434四阶斐波四阶斐波那契树那契树T4Fibonacci序列：序列：0，1，1，2，3，5，8，13，21，34，45数据结构国家精品课程2024/7/316阶斐波那契树，即阶斐波那契树，即N 12 f7 1. 9426234567891011120137511110128Fibon

36、acci序列：序列：0，1，1，2，3，5，8，13，21，34，46数据结构国家精品课程2024/7/31算法算法F(N，R，K.i)/*给给定定包包含含N个个记记录录R1，R2，RN，对对应应的的诸诸关关键键词词满满足足K1 K2 KN 的的表表，算算法法F查查找找变变元元K；为为方方便便计计，假假定定N fk+1 1，fk+1为为斐斐波波那那契契数数，只要适当初始化，算法只要适当初始化，算法F对任何对任何N 都有效都有效*/F1.初始化初始化置置if k ，pfk 1，qfk 2（p 和和q 是两个相邻的斐波那契数是两个相邻的斐波那契数，用于寻找下一次与，用于寻找下一次与K比较的点）比较

37、的点）.F2.比比较较若若K K i，则则转转步步骤骤F3；若若K K i，则则转转步步骤骤F4；若若K=K i，则算法成功结束，则算法成功结束.F3.i 减减值值若若q 0（已已到到树树叶叶），则则算算法法以以失失败败告告终终;否否则则置置ii q，t p，pq，q t q，并返回，并返回F2.F4.i 增增值值若若p 1（已已到到树树叶叶），则则算算法法以以失失败败告告终终;否否则则置置ii q，pp q，qq p，并返回，并返回F2.47数据结构国家精品课程2024/7/31引引理理8.4设设m3，Tm是是m阶阶Fibonacci树树形形，则则Tm的的左左子子树树形形的的高高度度等等于于

38、右右子子树树形形的的高高度度加加1，且且Tm的的高高度度为为m-1.引引理理8.5设设n=Fm+1-1，则则m阶阶Fibonacci树树形形的的高高度度约约等等于于1.44log2（n1）.定定理理8.2令令n=Fm+1-1，则则算算法法Fibonacci在在最最坏坏情情况况下下的的时间复杂性为时间复杂性为O(log2n)，且期望复杂性亦为，且期望复杂性亦为O(log2n).Fibonacci查找的算法分析查找的算法分析48数据结构国家精品课程2024/7/31Fibonacci查找算法的效率查找算法的效率l算法算法C的平均运行时间大约是算法的平均运行时间大约是算法F的的1.2倍，算倍，算法法

39、B的平均运行时间大约是算法的平均运行时间大约是算法F的的2.5倍。倍。l最坏情况下，算法最坏情况下，算法F比算法比算法C稍稍慢一点。稍稍慢一点。49数据结构国家精品课程2024/7/31小小结结若实现从有序表的顺序查找若实现从有序表的顺序查找到到对半查找算法对半查找算法B的的“跳跃跳跃”,必需必需实现实现:从只考虑从只考虑K Ki和和K Ki等两种情况等两种情况到到考虑考虑K Ki,K Ki和和K Ki等三种情况等三种情况;从每次比较下一个关键词从每次比较下一个关键词到到每次比较被每次比较被查找的子文件之中点。查找的子文件之中点。若实现从算法若实现从算法B到到一致对半查找算法一致对半查找算法U

40、的的“跳跃跳跃”,需实现一个需实现一个思想转弯思想转弯,即从使用即从使用s、e、i等等3个指针到仅使用个指针到仅使用i和和m两个指针两个指针（mm/2 ，下次被查找子文件长度之半）；，下次被查找子文件长度之半）；若实现从算法若实现从算法U到到一致对半查找算法一致对半查找算法C的的“跳跃跳跃”,需想到用一需想到用一张表存放诸张表存放诸m值值(算法运行时算法运行时,省去计算诸省去计算诸m的时间的时间,用空间换时用空间换时间间);当对半查找算法之改进当对半查找算法之改进到了到了“山重水复疑无路山重水复疑无路”的时候，跳出的时候，跳出对半二叉判定树的局限对半二叉判定树的局限转而去探索新的二叉判定树转而

41、去探索新的二叉判定树斐波那斐波那契二叉判定树，即斐波那契查找算法契二叉判定树，即斐波那契查找算法F.50数据结构国家精品课程2024/7/318.1线性表的查找线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找51数据结构国家精品课程2024/7/318.2.4插值查找插值查找问题的提出问题的提出l前前面面讨讨论论的的几几种种查查找找算算法法是是基基于于严严格格比比较较的的，即即假假定定我我们们对对线线性性表表中中元元素素的的分分

42、布布一一无无所所知知（或或称称没没有有启启发发式式信信息息）.然然而而实实际际中中，很很多多查查找找问问题题所所涉涉及及的的表表满满足足某某些些统统计的特点。计的特点。l例例如如在在一一本本英英汉汉字字典典中中寻寻找找单单词词“worst”，我我们们决决不不会会仿仿照照对对半半查查找找(或或Fibonacci查查找找)那那样样，先先查查找找字字典典中中间间的的元元素素，然然后后查查找找字字典典四四分分之之三三处处的的元元素素等等等等.事事实实上上，我我们们是是在在所所期期望望的的地地址址(在在字字典典的的很很靠靠后后的的地地方方)附附近近开开始始查找的，这样的查找为查找的，这样的查找为插值查找

43、插值查找.52数据结构国家精品课程2024/7/31插值查找基本思想插值查找基本思想l假假定定表表中中记记录录的的关关键键词词K1K2Kn在在(K0,Kn+1)区区间间上上呈呈均均匀匀分分布布.变变元元K给给定定，且且K0KKn+1，则则由由均均匀匀分分布布的的假假定定，我我们们可可用用线线性性插插值值来来决决定定K的的期期望望地地址址n(K-K0)/(Kn+1-K0).l若若KsK1ANDNOT(found)DO(m s+(e-s-1)(K-Ks)/(Ke-Ks) .IFKKmTHENem.IFKKmTHENsmIFK=KmTHENfoundtrue)54数据结构国家精品课程2024/7/3

44、1一、线性表的查找一、线性表的查找二、树形结构的查找二、树形结构的查找8.3二叉查找树二叉查找树8.4最优二叉查找树最优二叉查找树8.5高度平衡树高度平衡树8.7B树及其变型树及其变型三、散列三、散列55数据结构国家精品课程2024/7/318.3.1二叉查找树的基本概念和性质二叉查找树的基本概念和性质由由上上节节知知道道，一一株株隐隐含含的的二二叉叉树树结结构构有有助助于于了了解解对对半半查查找找和和斐斐波波那那契契查查找找之之特特性性。用用一一个个显显式式的的(explicit)二二叉叉树树结结构构，不不但但能能对对表表进进行行有有效效查查找找，而而且还能迅速插入和删除记录。且还能迅速插入

45、和删除记录。l定定义义8.1二二叉叉查查找找树树（又又称称为为二二叉叉搜搜索索树树、排排序序树树）TB是是一一棵棵可可为为空空的的二二叉叉树树，若若TB非非空空则则其其所所有有结结点点之之关关键键词词互互异异，且且中中根遍历根遍历TB形成按关键词递增序排列的结点序列。形成按关键词递增序排列的结点序列。l定定义义:一一棵棵二二叉叉查查找找树树是是一一棵棵可可能能为为空空的的二二叉叉树树形形，并并且且关关键键词词各各不不相相同同。二二叉叉查查找找树树中中的的任任一一结结点点P，它它的的左左子子树树中中结结点点的的关关键键词词都都小小于于KEY(P)，而而右右子子树树中中结结点点的的关关键键词词都都

46、大大于于KEY(P)，并且结点，并且结点P的左右子树也都是二叉查找树。的左右子树也都是二叉查找树。56数据结构国家精品课程2024/7/31二叉查找树和对半查找的二叉判定树的联系与区别。二叉查找树和对半查找的二叉判定树的联系与区别。OEAUIIEAUOIAEOUIAEOUIEAUO57数据结构国家精品课程2024/7/311、二叉查找树的结点结构：、二叉查找树的结点结构：LLINK和和RLINK是链接字段，是链接字段，KEY为该结点的关键词为该结点的关键词。2、基本操作、基本操作1）创建）创建2）查找）查找3）插入）插入4）删除）删除5）排序排序LLINKKEYDATARLINK58数据结构国

47、家精品课程2024/7/311、二叉查找树的查找、二叉查找树的查找算法算法BST(T,K.found)BST1由根结点开始由根结点开始PTfoundfalseBST2比较比较WHILEPnullANDNOT(found)DOCASEDO（KKEY（P）：）：PRLINK（P）.K=KEY（P）：）：foundtrue）59数据结构国家精品课程2024/7/31设设表表中中元元素素的的关关键键词词K1K2Kn，则则查查找找成成功功应应该该终终止止于于Ri(内内结结点点)，而而查查找找失失败败应应终终止止在在n1个个记记录录间间隔隔(或或者者称称外外结点，即结点，即KiKKi+1的情形的情形)。3

48、 35 56 61 12 2OOE EA AU UI I4 460数据结构国家精品课程2024/7/312 2、二叉查找树的创建、二叉查找树的创建n如何建立一棵二叉查找树。如何建立一棵二叉查找树。 例例 有一数据集合有一数据集合53,78,65,17,87,09,81,45,2353,78,65,17,87,09,81,45,23n给定各种查找情况发生的概率给定各种查找情况发生的概率i i和和i i，如何确定一棵如何确定一棵最优最优( (最小加权通路长度最小加权通路长度) )的二叉查找树的二叉查找树 ；( (静态树静态树) ) n近似最优树。近似最优树。61数据结构国家精品课程2024/7/3

49、13、二叉查找树的插入、二叉查找树的插入(动态树动态树) 35612OEAUI436712OEAUI5HH446712OEAUI3KK562数据结构国家精品课程2024/7/31设设树树形形T是是一一棵棵二二叉叉查查找找树树，T中中结结点点R1,R2,Rn相相应应的的关关键键词词满满足足K1K2Kn, 且且KiKKi+1, 0in(K0=-,Kn+1=+).那么插入新结点那么插入新结点K的过程就是用的过程就是用代替第代替第i+1个外结点的过程个外结点的过程.K63数据结构国家精品课程2024/7/31算法算法T(root,K.p)/*给给定定一一棵棵以以二二叉叉查查找找树树形形式式存存储储的的

50、记记录录表表，本本算算法法查查找找一一给给定定变变元元K.如如果果K不不在在表表中中，则则在在树树的的适适当当位位置置插插入入包包含含K的的一一个个新新结结点点。空空子子树树以以空空指指针针 表表示示，变变量量root指向此树的根。指向此树的根。*/T1.初始化初始化置置proot./指针指针p将沿树下移将沿树下移T2.比比较较如如果果Kkey(p)，则转到则转到T4；如果；如果K key(p)，则查找成功结束，则查找成功结束.64数据结构国家精品课程2024/7/31T3.左左移移如如果果llink(p) ，则则置置pllink(p)，并并转转回回T2；否则转到否则转到T5.T4.右右移移如

51、果如果rlink(p) ，则置，则置prlink(p)，并转回，并转回T2.T5.插入树形中插入树形中置置qAVAIL./q为新结点的地址为新结点的地址置置key(q)K，llink(q)rlink(q) .若若K key(p)，则置，则置llink(p)q，否则置，否则置rlink(p)q.置置pq，本算法成功结束，本算法成功结束65数据结构国家精品课程2024/7/31显显然然，算算法法T的的查查找找执执行行时时间间与与算算法法B同同阶阶（对对随随机机输输入入），即为即为O(log2N)66数据结构国家精品课程2024/7/314、二叉查找树的删除、二叉查找树的删除假假定定指指针针q指指向

52、向二二叉叉查查找找树树中中待待删删除除的的结结点点，则则删删除除q后的树仍为二叉查找树。后的树仍为二叉查找树。删删除除q后后，由由q的的中中根根后后继继或或者者中中根根前前驱驱结结点点代代替替q，删除过程分三种情形删除过程分三种情形:1)q无右儿子无右儿子；2)q有右儿子有右儿子r，但但r无左儿子无左儿子；3)q的右儿子的右儿子r有左儿子有左儿子。67数据结构国家精品课程2024/7/31二叉查找树的删除二叉查找树的删除l分三种情况加以讨论分三种情况加以讨论(删除删除q)：（1）rlink(q) .68数据结构国家精品课程2024/7/31372523751248608268961)1)q q

53、无无无无右右右右儿儿儿儿子子子子，此此此此时时时时用用用用q q的的的的左左左左儿儿儿儿子子子子代代代代替替替替q q所所所所指指指指结结结结点点点点( (例如删除例如删除例如删除例如删除23)23)。二叉查找树的删除（情况一）二叉查找树的删除（情况一）二叉查找树的删除（情况一）二叉查找树的删除（情况一）37257512486082689669数据结构国家精品课程2024/7/31二叉查找树的删除二叉查找树的删除l分三种情况加以讨论分三种情况加以讨论(删除删除q)：（2）rlink(q) ，且，且llink(rlink(q) 70数据结构国家精品课程2024/7/313725237512486

54、08268962)2)q q有有有有右右右右儿儿儿儿子子子子r r，但但但但r r无无无无左左左左儿儿儿儿子子子子，用用用用以以以以r r为为为为根根根根的的的的子子子子树树树树取代取代取代取代qq；(例如删除例如删除例如删除例如删除75)75)二叉查找树的删除（情况二）二叉查找树的删除（情况二）37252312486082689671数据结构国家精品课程2024/7/31二叉查找树的删除二叉查找树的删除l分三种情况加以讨论分三种情况加以讨论(删除删除q)：（3）rlink(q) ，且，且llink(rlink(q) .72数据结构国家精品课程2024/7/313725237512486082

55、68963 3) )q q的的的的右右右右儿儿儿儿子子子子r r有有有有左左左左儿儿儿儿子子子子，以以以以该该该该左左左左儿儿儿儿子子子子为为为为根根根根的的的的子子子子树树树树的的的的最最最最左左左左下下下下结结结结点点点点 s s取取取取 代代代代 q q， 同同同同时时时时将将将将s s的的的的父父父父结结结结点点点点指指指指向向向向原原原原s s的的的的右右右右子子子子树。树。树。树。(例如删除例如删除例如删除例如删除25)25)二叉查找树的删除（情况三）二叉查找树的删除（情况三）二叉查找树的删除（情况三）二叉查找树的删除（情况三）37237512486082689673数据结构国家精

56、品课程2024/7/31算法算法D( q，a.)/*删除二叉查找树中的结点删除二叉查找树中的结点q,指针指针a指向结点指向结点q的父亲。的父亲。*/D1.rlink(q) tq.若若rlink(t) ，则则tllink(t)，并转到步骤并转到步骤D4./t指向取代指向取代q位置的结点位置的结点D2.llink(rlink(q) rrlink(t).若若llink(r) ，则，则llink(r)llink(q)，tr，转，转D4.D3.llink(rlink(q) sllink(r).若若llink(s) ，则则rs并重复到并重复到llink(s) 为止为止.置置llink(s)llink(t)

57、，llink(r)rlink(s)，rlink(s)rlink(t)，ts.D4.接树与释放结点接树与释放结点q若若llink(a) q，则，则llink(a)t；否则；否则rlink(a)t.然后置然后置AVAILq.74数据结构国家精品课程2024/7/31二叉查找树的简单分析二叉查找树的简单分析l由由于于算算法法D左左右右两两边边很很不不对对称称，有有理理由由认认为为一一连连串串的的随随机机删删除除和和插插入入操操作作将将使使树树失失去去平平衡衡，但但事事实实上上，删删除操作不会使树退化。除操作不会使树退化。l定定理理8.3（T.N.Hibbard，1962）通通过过算算法法D从从一一株

58、株随随机机二二叉叉查查找找树树中中删删除除一一个个随随机机元元素素之之后后，得得到到的的树树仍是随机的。仍是随机的。l结结论论:在在随随机机情情况况下下，二二叉叉查查找找树树操操作作的的平平均均时时间间为为O (log2N)但但在在特特定定情情况况下下，会会产产生生形形同同线线性性链链表表的的退退化化的的二二叉叉查查找找树树形形，从从而而使使最最坏坏情情况况查查找找时时间间达达O(N).75数据结构国家精品课程2024/7/31二、树形结构的查找二、树形结构的查找8.3二叉查找树二叉查找树8.4最优二叉查找树最优二叉查找树8.5高度平衡树高度平衡树8.7B树及其变型树及其变型76数据结构国家精

59、品课程2024/7/31静态树静态树给定各种查找情况发生的概率给定各种查找情况发生的概率i和和i，如何确定一棵最优如何确定一棵最优(最最小加权通路长度小加权通路长度)的二叉查找树的二叉查找树；动态树动态树建立最优二叉查找树；建立最优二叉查找树；对对树动态调整，保证动态插入删除结点后，仍为最优。树动态调整，保证动态插入删除结点后，仍为最优。缺点：计算复杂度高，有时结点出现的频率无法精确统计。缺点：计算复杂度高，有时结点出现的频率无法精确统计。解决方案：构造解决方案：构造近似最优或较优近似最优或较优的二叉查找树。的二叉查找树。77数据结构国家精品课程2024/7/31二、树形结构的查找二、树形结构

60、的查找8.3二叉查找树二叉查找树8.4最优二叉查找树最优二叉查找树8.5平衡树平衡树8.7B树及其变型树及其变型78数据结构国家精品课程2024/7/318.5.1高度平衡树高度平衡树l定义定义8.2：一棵二叉查找树称为：一棵二叉查找树称为高度平衡二叉查找树高度平衡二叉查找树（高度平衡树、平衡树）（高度平衡树、平衡树），当且仅当或者由单一的外，当且仅当或者由单一的外结点组成，或者由两个子树形结点组成，或者由两个子树形Tl和和Tr组成，且满足：组成，且满足：(1)|h(Tl)h(Tr)|1，其中其中h(T)表示树表示树T的高度；的高度；(2)Tl和和Tr都是高度平衡树都是高度平衡树.l高高度度平

61、平衡衡树树是是最最佳佳二二叉叉查查找找树树和和任任意意二二叉叉查查找找树树的的一一种折中方案。种折中方案。79数据结构国家精品课程2024/7/31l定定义义8.3设设T为为增增长长二二叉叉树树，q是是T之之内内结结点点，qL 和和qR 是是q的的左左、右右子子树树，hL和和hR 分分别别是是qL和和qR 的的高高度度，q的的平衡系数平衡系数（或曰（或曰平衡因子平衡因子）BF(q)定义为定义为hR hL.l高度平衡树的结点结构：高度平衡树的结点结构：B为平衡系数。为平衡系数。lFibonacci判判定定树树形形是是一一棵棵高高度度平平衡衡树树，且且每每个个结结点点（以以该该结结点点为为根根的的

62、二二叉叉树树的的内内结结点点数数 2）的的平平衡衡系系数为数为 1。KEYDATABLLINKRLINK80数据结构国家精品课程2024/7/31树形总高度树形总高度RLINK(HEAD)HEADKEY (ROOT)B(ROOT)LLINK(ROOT)RLINK(ROOT)ROOT81数据结构国家精品课程2024/7/31平衡树的定义表达了最优二叉树（所有外结点都在两个相平衡树的定义表达了最优二叉树（所有外结点都在两个相邻的层上）和任意二叉树之间的折中。人们自然要问，一邻的层上）和任意二叉树之间的折中。人们自然要问，一棵平衡树比最优树差多少。答案是，平衡树的查找路径长棵平衡树比最优树差多少。答

63、案是，平衡树的查找路径长度决不会超过最优树的查找路径长度的度决不会超过最优树的查找路径长度的45%.定理定理8.4(Adelson-Velsky和和Landis)设设T是一棵具有是一棵具有N个内结个内结点的平衡树，点的平衡树，T之高度之高度h (T)由下式所限定由下式所限定log2(N+1) h(T) 1.4404 log2(N+2) 0.3277.82数据结构国家精品课程2024/7/312、高度平衡树的插入操作高度平衡树的插入操作l平衡性将遭到破坏平衡性将遭到破坏：平衡系数为平衡系数为+1的结点，如果在它的右子树的外结点上插入新的结点，如果在它的右子树的外结点上插入新结点结点，使它的右子树

64、变得更高使它的右子树变得更高平衡系数为平衡系数为 1的结点，如果在它的左子树的叶结点上插入新的结点，如果在它的左子树的叶结点上插入新结点结点，使它的左子树变得更高使它的左子树变得更高83数据结构国家精品课程2024/7/31(a)情况情况1(b)情况情况2 高度平衡树的调整高度平衡树的调整 BAhhh 1hh A BXh 1ha 84数据结构国家精品课程2024/7/31情况情况1：“单一转动单一转动” 结点结点 B 从从A 的右下侧的右下侧左转左转到到A 的右上侧，原的右上侧，原 B 之左子之左子树形变成了树形变成了A 的右子树形，的右子树形，B 的新左儿子是结点的新左儿子是结点A . BA

65、hhh 1插入前以插入前以A为根的子树高度为为根的子树高度为h 2，插入后变换前，其，插入后变换前，其高度高度h 3变换后，变成了以变换后，变成了以B为根的子树，其高度为为根的子树，其高度为h 2.85数据结构国家精品课程2024/7/31情况情况2：“双重转动双重转动” hh A BXh 1ha 插入前以插入前以A为根的子树高度为为根的子树高度为h 2，插入后变换前，其，插入后变换前，其高度高度h 3变换后，变成了以变换后，变成了以X为根的子树，其高度为为根的子树，其高度为h 2.86数据结构国家精品课程2024/7/31hh A BXh 1ha AhXh 1a h Bh 以以X 为轴将为轴

66、将B 从从X 的右上侧的右上侧右转右转到到X 的右下侧，记为（的右下侧，记为（X，B），从而），从而A 的右儿子是的右儿子是X，X 的右儿子是的右儿子是B，原，原X 的的右子树变成了新右子树变成了新B 的左子树；的左子树；87数据结构国家精品课程2024/7/31hAXh 1a h Bh AXha h Bh h 1以以X 为轴心为轴心,把把A 从从X 的左上方转到的左上方转到X 的左下侧的左下侧,记为记为(A ,X),使使X 的左儿子是的左儿子是A ,右儿子是右儿子是B ,原原X 的左子树变成了的左子树变成了A的右子树的右子树. 88数据结构国家精品课程2024/7/31n经过插入与调整后，以

67、经过插入与调整后，以A 为根的子树变成了一棵与插入前为根的子树变成了一棵与插入前有同样高度的新树。有同样高度的新树。n原先以结点原先以结点A 为根的子树之外的所有内结点都与插入前有为根的子树之外的所有内结点都与插入前有相同的平衡系数，是保持平衡的。相同的平衡系数，是保持平衡的。n插入新结点插入新结点n后，若树失去平衡，应调整失去平衡的最小子后，若树失去平衡，应调整失去平衡的最小子树。为了找到失去平衡的最小子树，我们可以记录从根结点树。为了找到失去平衡的最小子树，我们可以记录从根结点r到结点到结点n的一条路径，在该路径上寻找从下向上的第一个平的一条路径，在该路径上寻找从下向上的第一个平衡系数非零

68、的结点衡系数非零的结点A；A确定后，重新平衡以确定后，重新平衡以A为根的子树为根的子树形可。形可。89数据结构国家精品课程2024/7/31高度平衡树的插入与调整算法高度平衡树的插入与调整算法(略略)rf f. . .A(+-)A(+-)n90数据结构国家精品课程2024/7/31l例：构造包含关键词例：构造包含关键词20，35，40，15，30，25高高度平衡树。度平衡树。91数据结构国家精品课程2024/7/31构造包含关键词构造包含关键词20，35，40，15，30，25高度平衡树。高度平衡树。92数据结构国家精品课程2024/7/313、高度平衡树的删除操作、高度平衡树的删除操作l高高

69、度度平平衡衡树树的的删删除除操操作作，被被删删除除结结点点的的祖祖先先结结点点的的平平衡衡系系数数均有可能发生变化。均有可能发生变化。l算算法法将将从从根根结结点点到到被被删删除除结结点点路路径径上上的的所所有有结结点点依依次次入入栈栈，设设指指针针son指指向向被被删删除除结结点点，current是是son的的父父结结点点，则则按按照照如下的规则进行删除：如下的规则进行删除：1)如如果果B(current)=0,且且son=LLINK(current),则则B(current)+l,否则否则B(current)-1.并终止整个过程并终止整个过程.93数据结构国家精品课程2024/7/312)

70、如如果果B(current)=+1且且son=RLINK(current),或或B(current)=-1且且son=LLINK(current),则则B(current)=0,且且current的的高高度度减减1.此时令此时令soncurrent,currentS,然后继续然后继续.3)如如果果B(current)=+1且且son=LLINK(current)，则则此此时时current的的平平衡衡系系数数等等于于+2，因因此此根根据据RLINK(current)的的平平衡衡系系数数来来进进行行重重新新平平衡衡操操作作，若若调调整整后后树树高高度度不不变变，则则算算法法终终止止；若若调整后树

71、高度减调整后树高度减1，则令，则令soncurrent,currentS,然后继续然后继续.4)如如果果B(current)=-1且且son=RLINK(current)，则则此此时时所所发发生生的情况正好是的情况正好是(3)所示情况的对称情形所示情况的对称情形.94数据结构国家精品课程2024/7/31平衡树的平衡树的删除操作删除操作如如果果采采用用正正确确的的方方法法，则则删删除除问问题题可可以以在在O(log2N)步步骤骤内内解决解决；删删除除和和插插入入之之间间的的重重要要差差别别是是：删删除除可可能能需需要要多多达达平平均均log2N 次调整，而插入所需的调整不多于次调整，而插入所需

72、的调整不多于1次次。95数据结构国家精品课程2024/7/314、线性表的平衡树表示、线性表的平衡树表示用平衡树来表达线性表，既可快速地插入（克服顺序分配的困用平衡树来表达线性表，既可快速地插入（克服顺序分配的困难），又可对表实施随机存取（克服链接分配的困难）。难），又可对表实施随机存取（克服链接分配的困难）。在每一个结点在每一个结点P增加一个被称之为增加一个被称之为RANK的字段的字段l RANK(P) P的左子树形的的左子树形的(内内)结点数结点数 1lRANK域之值确定了结点的域之值确定了结点的相对相对位置位置96数据结构国家精品课程2024/7/31RANK域之值确定了结点的相对位置域

73、之值确定了结点的相对位置若若k 6，则所查找的结点为，则所查找的结点为NODE(F)；若若k6，则往右去检索，则往右去检索如如k 8，则，则NODE(H)便是所求，因便是所求，因RANK(H) k 6 2.NODE(E)在中根次序下的位置是在中根次序下的位置是5，它等于，它等于RANK(D) 1；NODE(K)的的位位置置（中中序序）是是11，它它等等于于RANK(F) RANK(K) 6 597数据结构国家精品课程2024/7/31树形总高度树形总高度RLINK(HEAD)HEADRLINKLLINKB RANKDATA(KEY)ROOT98数据结构国家精品课程2024/7/31算法算法B(

74、HEAD，k.)/*给定给定表示成一株二叉树的线性表表示成一株二叉树的线性表和变元和变元k，本算法查找在中根次序，本算法查找在中根次序下该表的第下该表的第k个元素。个元素。*/B1初始化初始化置置M k，PRLINK(HEAD)/*P指向根指向根ROOT*/.B2比较比较若若P ，则算法以失败告终，则算法以失败告终/*k树中结点数或树中结点数或k 0*/.若若MRANK(P)，则转到步骤，则转到步骤B4/*向右向右*/；若若M RANK(P)，则本算法成功地结束，则本算法成功地结束.B3左移左移置置PLLINK(P)并返回步骤并返回步骤B2.B4右移右移置置MM RANK(P)，PRLINK(

75、P)并返回步骤并返回步骤B2.99数据结构国家精品课程2024/7/31二、树形结构的查找二、树形结构的查找8.3二叉查找树二叉查找树8.4最优二叉查找树最优二叉查找树8.5高度平衡树高度平衡树8.7B树及其变型树及其变型100数据结构国家精品课程2024/7/318.7B树及其变形树树及其变形树前前面面介介绍绍的的树树形形查查找找方方法法，主主要要属属于于内内查查找找方方法法，适适用用于于被被检检索索文文件件能能完完整整地地被被放放到到计计算算机机内内存存中中的的情情形形。如如果果文文件件很很大大，以以至至于于计计算算机机内内存存容容纳纳不不下下时时，则则必必须须放放在在磁磁盘盘等等外外存存

76、储储器器上上。当当人人们们想想从从一一个个存存放放在在磁磁盘盘上上的的大大文文件件中中查查找找某某些信息时，则需要去研究一种新的查找方法些信息时，则需要去研究一种新的查找方法外查找外查找。101数据结构国家精品课程2024/7/318.7.1多叉树多叉树102数据结构国家精品课程2024/7/311、基本概念、基本概念1970年，拜尔年，拜尔(R.Bayer)和麦克瑞特和麦克瑞特(E.McCreight)提出一种提出一种新的新的外查找树外查找树，称为，称为B树。这是一种树。这是一种多叉平衡树形多叉平衡树形，它在插，它在插入或删除操作中有简单的平衡算法。入或删除操作中有简单的平衡算法。B树及它的

77、一些改进形树及它的一些改进形式已成为索引文件的有效结构，得到了广泛的应用。式已成为索引文件的有效结构，得到了广泛的应用。定义定义8.7一个一个m阶的阶的B树树满足下述条件：满足下述条件：1.每个结点有每个结点有 m个儿子；个儿子；2.除根和叶之外的每个结点有除根和叶之外的每个结点有 m/2 个儿子；个儿子；3.根结点至少要有两个儿子（除非它本身又是一个叶结点）；根结点至少要有两个儿子（除非它本身又是一个叶结点）；4.具有具有k 个儿子的非叶结点包含个儿子的非叶结点包含k 1个关键词；个关键词；5.所有的叶结点都出现在同一层上，并且它们都不带有信息所有的叶结点都出现在同一层上，并且它们都不带有信

78、息.8.7.2B树树103数据结构国家精品课程2024/7/31233449031097137191 011017023041047059067073083103109127149157167179197211227283353401241257269277307313331347367379389419431439499599677773829883919907937947967461467487509523547563571587607617631643653661691709727739751761797811823853859877一个一个7阶阶B树，其所有的叶都在第树，其所有的叶都在

79、第3层上层上叶叶不不带带有有信信息息，可可以以认认为为它它们们是是外外部部结结点点，实实际际上上它它们们不不在在树树中中，所所以以指指向向叶叶的的指针为空。指针为空。104数据结构国家精品课程2024/7/31031097137191011017023179197211227103109127149157167083073067059047041105数据结构国家精品课程2024/7/31在在前前面面的的7阶阶B树树中中，每每个个结结点点(除除了了根根和和叶叶)，有有 7/2 到到7个个儿儿子子，故故可可有有3，4，5或或6个个关关键键词词。根根结结点点允允许许有有1至至6个个关关键键词，根结

80、点包含两个关键词。这个词，根结点包含两个关键词。这个B树的所有叶子都在第树的所有叶子都在第3层上。层上。应强调指出的是：应强调指出的是：每个非叶结点中的关键词是按从左到右的递增顺序排列的；每个非叶结点中的关键词是按从左到右的递增顺序排列的；叶子的总数比关键词总数多叶子的总数比关键词总数多1；和和两点表明了两点表明了B树是二叉查找树的一个自然推广。树是二叉查找树的一个自然推广。很很自自然然，我我们们对对1阶阶和和2阶阶B树树毫毫无无兴兴趣趣，这这里里只只考考虑虑m 3的的情况。阶为情况。阶为3的的B树，也叫做树，也叫做2-3树。树。106数据结构国家精品课程2024/7/31一个包含一个包含j个

81、关键词和个关键词和j+1个指针的个指针的B树结点如图所示。结点树结点如图所示。结点之关键词满足之关键词满足K1 K2 Kj，指针，指针Pi 指向一个其所有关键指向一个其所有关键词都在词都在K i和和Ki+1之间的子树形。因此，在之间的子树形。因此，在B树中进行查找树中进行查找是十分是十分简单的。简单的。P0K1P1K2P2Pj 1KjPjB-树的结点树的结点P107数据结构国家精品课程2024/7/312、查找、查找假假定定结结点点P已已从从磁磁盘盘读读到到内内存存中中，可可选选择择适适当当的的内内查查找找方方法法。当当j 比比较较大大时时，可可选选择择对对半半查查找找算算法法；当当j 较较小

82、小时时可可采采用用顺顺序序查查找找方方法法。设设查查找找一一个个给给定定的的变变元元k ，若若k在在NODE(P)中中，则则查找成功。否则必是下述三种情形之一：查找成功。否则必是下述三种情形之一：1)K i k Ki+1(1 i j)，则继续到结点，则继续到结点NODE(Pi)中去查找中去查找.2)k Kj ，查找将转，查找将转NODE(P j)继续查找。继续查找。3)k K1，查找将转，查找将转NODE(P0)继续查找。继续查找。如如果果指指向向下下一一个个要要查查找找的的结结点点的的指指针针Pi= ，则则查查找找以以失失败败告告终，关键词为终，关键词为k 的记录不在树中。的记录不在树中。1

83、08数据结构国家精品课程2024/7/313、插入、插入（1）若若在在一一个个包包含含j m 1个个关关键键词词的的结结点点中中插插入入一一个个新新关关键键词词，则则插插入入过过程程将将局局限限于于该该结结点点自自身身（把把新新关关键键词词直直接接插插入入该该结结点点中中即即可可）。如如在在下下图图中中插插入入关关键键词词337，只只须须改改变变一个结点即可。一个结点即可。347337331313307347331313307109数据结构国家精品课程2024/7/31插入插入（2）若若把把一一个个新新关关键键词词插插入入一一个个已已包包含含m 1个个(m为为B树树的的阶阶)关关键键词词的的结

84、结点点(结结点点已已满满)，则则插插入入将将造造成成此此结结点点“分分裂裂”。如如插插入入关关键键词词071。此此时时，把把m个个关关键键词词分分成成个个数数相相等等的的两两组组，第第一一组组从从左左向向右右数数，包包含含 m/2 个个关关键键词词，第第二二组组从从右右向向左左数数，包包含含 m/2 个个关关键键词词，剩剩下下的的中中间间那个关键词将被提升到上一层结点中，去开始新的插入。那个关键词将被提升到上一层结点中，去开始新的插入。“分分裂裂”可可能能会会向向上上传传播播，在在极极端端情情况况下下，分分裂裂会会一一直直波波及及到到根根结结点点，而这恰恰是而这恰恰是B树长高的唯一方式。树长高

85、的唯一方式。031097137191083073067059047041031097137191067041047059071073083110数据结构国家精品课程2024/7/314、删除、删除先先找找到到要要删删除除的的关关键键词词Ki的的位位置置，若若它它不不在在叶叶的的上上一一层层里里，则则要要把把删删除除Ki后后的的空空位位置置用用最最接接近近Ki而而又又大大于于Ki的的关关键键词词K*来来填填充充，同同时时从从K*所所在在的的结结点点中中删删除除K*，这这是是因因为为在在中中间间诸诸层层的的关键词还起指导向下查找的作用，故不能为空。例如删除关键词还起指导向下查找的作用，故不能为空。

86、例如删除353。347367379389307313331283353401379389307313331283367401111数据结构国家精品课程2024/7/31当当删删除除关关键键词词后后，空空位位置置已已在在B树树之之叶叶子子的的上上一一层层结结点点中中。要要检查该结点目前包含的关键词个数是否小于检查该结点目前包含的关键词个数是否小于 m/2 -1.(1)若不是，则直接删除空位置，即合并两个空指针。若不是，则直接删除空位置，即合并两个空指针。(2)若若是是，则则要要从从相相邻邻的的兄兄弟弟结结点点中中借借关关键键词词，最最好好使使两两个个结结点点的的大大小小一一样样（即即包包含含相相

87、同同数数目目的的关关键键词词）。如如下下图图删删除除关关键键词词379的情形。的情形。347367379389307313331283353401353367389307313331283347401112数据结构国家精品课程2024/7/31若若相相邻邻（同同父父）结结点点的的关关键键词词个个数数都都等等于于 m/21，则则一一个个与与分分裂裂相相反反的的过过程程“合合并并”便便发发生生了了。所所谓谓“合合并并”，即即把把两两个个兄兄弟弟结结点点的的关关键键词词连连同同在在父父结结点点中中指指向向这这两两个个结结点点的的指指针针之之间间的的关关键键词词按按递递增增顺顺序序排排列列在在一一个个

88、新新结点中。例如从上图中删去关键词结点中。例如从上图中删去关键词431。若若“合合并并”操操作作使使上上一一层层结结点点（父父结结点点）所所包包含含的的关关键键词词个个数数出出现现了了 m/21的的情情况况，则则又又造造成成了了上上一一层层结结点点或或要要借借关关键键词词或或要要进进行行“合合并并”操操作作。“合合并并”可可能能会会导导致致上上一一层层发发生生“合合并并”，从从而而可可能能使使“合合并并”不不断断向上传播，或许一直波及到根结点，从而有可能使整个向上传播，或许一直波及到根结点，从而有可能使整个B树减少一层。树减少一层。 283353401419431439367379389283

89、353439419401389379367113数据结构国家精品课程2024/7/315、讨论、讨论设设有有一一个个m 阶阶B树树，它它包包含含N个个关关键键词词，它它的的N+1个个叶叶子子出出现现在第在第l 层上。则：层上。则：这这意意味味着着，当当N=1999998且且m=199时时，l 最最多多是是3.就就是是说说，在在最最坏坏的的情情况况下下，一一次次查查找找至至多多需需要要存存取取3个个结结点点。因因此此，B树上的查找操作是很快的。树上的查找操作是很快的。114数据结构国家精品课程2024/7/318.7.3B+树树由由于于B树树的的结结点点代代表表一一个个辅辅存存页页或或者者是是一

90、一个个辅辅存存块块，从从一一个个结结点点到到另另一一个个结结点点需需要要费费时时的的页页切切换换。所所以以最最好好尽尽可可能能地地少少访问结点。访问结点。如如果果请请求求以以升升序序访访问问B树树中中的的结结点点，如如用用中中序序遍遍历历，但但对对非非末末端端结结点点，一一次次只只能能显显示示一一个个关关键键词词，然然后后就就要要访访问问其其他他的的页页。因因此此，希希望望增增强强B树树，能能以以比比中中序序遍遍历历快快的的方方式式顺顺序序访访问问数据。数据。B+树提供了一个解决方案。树提供了一个解决方案。115数据结构国家精品课程2024/7/31B+树树是是适适应应文文件件系系统统的的需需

91、要要而而产产生生的的一一种种B树树的的变变形形树树，一一棵棵m阶阶B+树须满足下列条件：树须满足下列条件：1)每个分支结点至多有每个分支结点至多有m棵子树；棵子树；2)除根结点外，其它每个分支结点至少有除根结点外，其它每个分支结点至少有 m/2 棵子树；棵子树；3)根结点至少有两棵子树，至多有根结点至少有两棵子树，至多有m棵子树；棵子树；4)有有n棵子树的结点有棵子树的结点有n个关键词；个关键词；5)所所有有的的叶叶子子结结点点包包含含全全部部关关键键词词及及指指向向相相应应记记录录的的指指针针，而而且叶子结点按关键词自小而大的顺序链接；且叶子结点按关键词自小而大的顺序链接；6)所所有有分分支

92、支结结点点（可可看看成成是是索索引引的的索索引引）中中仅仅包包含含它它的的各各个个子子结点（下级索引的索引块）中最大关键词及指向子结点的指针。结点（下级索引的索引块）中最大关键词及指向子结点的指针。116数据结构国家精品课程2024/7/31一棵一棵2阶阶B+树树70954070951020204091953540517044518591657093955101120403035444751616570808591929395117数据结构国家精品课程2024/7/31一棵一棵m阶阶B+树和一棵树和一棵m阶阶B树的差异在于树的差异在于:B 树中，有树中，有n棵子树的结点中含有棵子树的结点中含有

93、n个关键词；个关键词；B 树树中中，每每个个结结点点（根根结结点点和和叶叶结结点点除除外外）中中的的关关键键词词个个数数n的的取取值值范范围围是是 m/2n m，根根结结点点关关键键词词个个数数n的的取取值值范范围围是是2 n m；而而B树树中中，它它们们的的取取值值范范围围分分别别是是 m/21 n m 1和和1 n m 1；B 树树中中，所所有有的的叶叶结结点点中中包包含含了了全全部部关关键键词词，即即其其它它非非叶叶结结点点中中的的关关键键词词都都包包含含在在叶叶结结点点中中；而而在在B树树中中，叶叶子子结结点点包包含含的的关关键键词与其它结点包含的关键词是不重复的；词与其它结点包含的关

94、键词是不重复的；B 树树中中，非非叶叶结结点点仅仅起起索索引引作作用用，即即结结点点中中每每个个索索引引项项只只含含有有对对应应子子树树的的最最大大关关键键词词和和指指向向该该子子树树的的指指针针，不不含含有有该该关关键键词词对对应应记录的存储地址。而记录的存储地址。而B树中，每个关键词对应一个记录的存储地址；树中，每个关键词对应一个记录的存储地址；通通常常在在B 树树上上有有两两个个头头指指针针，一一个个指指向向根根结结点点，另另一一个个指指向向最最小关键词的叶子结点，所有叶子结点链接成一个不定长的线性链表。小关键词的叶子结点，所有叶子结点链接成一个不定长的线性链表。118数据结构国家精品课

95、程2024/7/31B+树树进进行行两两种种查查找找运运算算：一一种种是是从从最最小小关关键键词词开开始始进进行行顺序查找，另一种是从根结点开始进行随机查找。顺序查找，另一种是从根结点开始进行随机查找。在在B+树树上上进进行行随随机机查查找找、插插入入和和删删除除操操作作的的过过程程基基本本上上与与B树树类类似似。只只是是在在查查找找时时，如如果果非非叶叶结结点点上上的的关关键键词词等等于于给给定定值值，并并不不终终止止，而而是是继继续续向向下下直直到到叶叶结结点点。因因此此，在在B+树树中中，不不管管查查找找成成功功与与否否，每每次次查查找找都都是是走走了了一一条条从从根根到到叶叶结点的路径

96、。结点的路径。119数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找二、树形结构的查找二、树形结构的查找三、散列三、散列(杂凑杂凑)8.9.1散列表散列表(杂凑表杂凑表)的定义的定义8.9.2散列函数的构造散列函数的构造8.9.3冲突调解冲突调解120数据结构国家精品课程2024/7/31l目目前前，我我们们所所考考虑虑的的查查找找方方法法在在找找到到以以K为为关关键键词的记录之前，都要检查若干数目的关键词词的记录之前，都要检查若干数目的关键词.l杂杂凑凑技技术术则则完完全全免免去去了了上上述述方方法法所所作作的的搜搜索索，由由给给定定变变元元K直直接接计计算算出出函函数

97、数值值f(K)，而而f(K)即即为为包包含含K的记录所在的地址的记录所在的地址.l杂凑函数满足的条件：杂凑函数满足的条件：1.便于快速计算；便于快速计算；2.极少出现冲突极少出现冲突(函数是均匀的函数是均匀的).121数据结构国家精品课程2024/7/31l杂杂凑凑表表(散散列列表表)：根根据据给给定定的的杂杂凑凑函函数数Hash(Key)和和处处理理冲冲突突的的方方法法，将将一一组组关关键键词词映映射射到到一一个个有有限限的的连连续续的的地地址址区区间间上上，并并以以关关键键词词在在地地址址集集上上的的“映映像像”作作为为该该记记录录在在表表中中的的存存储储位位置置，这这种种表表称称为为杂杂

98、凑凑表表或或者者散散列列表表。这这种种映映射射过过程程称称为为杂杂凑凑，所所得得到到的的存存储储位位置置称为称为杂凑地址或者散列地址杂凑地址或者散列地址。122数据结构国家精品课程2024/7/31 杂凑技术避免了关键词的比较杂凑技术避免了关键词的比较 杂凑技术的关键：杂凑技术的关键：如何构造均匀的杂凑函数如何构造均匀的杂凑函数解决冲突的方法解决冲突的方法123数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找二、树形结构的查找二、树形结构的查找三、散列三、散列(杂凑杂凑)8.9.1散列表散列表(杂凑表杂凑表)的定义的定义8.9.2散列函数的构造散列函数的构造8.9.3冲突

99、调解冲突调解124数据结构国家精品课程2024/7/312、杂凑函数杂凑函数l杂杂凑凑函函数数h与与组组成成关关键键词词K的的符符号号有有关关.如如果果K是是从从关关键键词词集集合合中中随随机机选选取取的的一一个个，则则我我们们希希望望h(K)以以同同等等概概率率取取区区间间0，M-1中中的的每每一一个个值值.如如果果一一个个杂杂凑凑函函数数满满足足这这一一性性质质，则则被称为是被称为是均匀均匀的的.l为为了了方方便便，我我们们把把关关键键词词表表示示为为二二进进制制代代码码.例例如如，可可把把每每个个英英文文字字母母看看成成一一个个5位位二二进进制制数数，即即令令A=00001，B=0001

100、0，C=00011，Z=11010.从从而而每每个个单单词词是是一一个个连连续续的的二二进进制串，比如制串，比如THE表示为串表示为串h(THE)=101000100000101THE125数据结构国家精品课程2024/7/31l构造杂凑函数方法构造杂凑函数方法1.抽取法抽取法2.压缩法压缩法3.除法杂凑函数除法杂凑函数4.乘法杂凑函数乘法杂凑函数126数据结构国家精品课程2024/7/31l构造杂凑函数方法构造杂凑函数方法1.抽取法抽取法从从关关键键词词相相对对的的二二进进制制串串中中抽抽取取几几个个分分散散的的代代码码，然然后合并这几个代码，形成一个地址后合并这几个代码，形成一个地址.例例

101、抽取法抽取第三位和最后两位作为杂凑地址，则抽取法抽取第三位和最后两位作为杂凑地址，则h(THE)=101000100000101=101THE127数据结构国家精品课程2024/7/312.压缩法压缩法把把关关键键词词的的二二进进制制串串分分割割成成若若干干个个子子串串，然然后后按按某某种种方式把这些子串合并，形成该关键词的地址方式把这些子串合并，形成该关键词的地址.例例：h(THE)=10100XOR01000XOR00101=110012510异或运算满足交换律，即有同样字母的单词有相同的异或运算满足交换律，即有同样字母的单词有相同的杂凑地址。杂凑地址。h(STEAL)=h(STALE)=

102、h(TALES)=h(LEAST)128数据结构国家精品课程2024/7/313.除法杂凑函数除法杂凑函数h(K)=KmodM，其其中中K为为记记录录的的关关键键词词，M为为杂杂凑表容量。凑表容量。例：例：h(THE)=101000100000101mod31=2074110mod31=2注意合理选择注意合理选择M值，值，M一般为素数。一般为素数。129数据结构国家精品课程2024/7/314.乘法杂凑函数乘法杂凑函数给给定定一一个个实实数数，01，则则按按如如下下的的方方式式给给出出一一个杂凑函数个杂凑函数.H(K)= M(Kmod1) 一一般般来来说说，当当0.6180339887或或=0

103、.3819660113时，杂凑函数能均匀地分布在时，杂凑函数能均匀地分布在0，M-1上上.130数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找二、树形结构的查找二、树形结构的查找三、散列三、散列(杂凑杂凑)8.9.1散列表散列表(杂凑表杂凑表)的定义的定义8.9.2散列函数的构造散列函数的构造8.9.3冲突调解冲突调解131数据结构国家精品课程2024/7/313、冲突调节、冲突调节l冲突调节方法冲突调节方法1.拉链法拉链法2.线性探查线性探查3.双重杂凑双重杂凑132数据结构国家精品课程2024/7/311.拉链法拉链法假假定定表表T包包含含M个个散散列列地地址址T0

104、，Tl，TM-l，拉拉链链就就是是令令散散列列地地址址等等于于i的的记记录录组组成成一一个个链链表表，且且指指针针Ti是是该该单链表的头指针单链表的头指针.133数据结构国家精品课程2024/7/31l为为了了节节约约存存储储空空间间，改改进进的的方方法法是是将将每每个个Ti分分成成两两个个域域，一一个个域域存存放放记记录录，另另一一个个域域为为LINK，存存放放指指针针，指指向向具具有有相同杂凑地址的下一个记录。相同杂凑地址的下一个记录。l当当插插入入关关键键词词K时时，如如若若发发现现Th(K)处处已已包包含含别别的的记记录录，则则沿沿LINK一一直直找找下下去去，直直到到一一个个表表地地

105、址址的的LINK值值为为空空然然后后找找到到一一个个空空的的表表地地址址Tfree，把把K存存储储在在Tfree处处，并并置置最最后一个空后一个空LINK域的值为域的值为freel寻找空地址可由寻找空地址可由TM-l开始，向开始，向T0方向搜索方向搜索134数据结构国家精品课程2024/7/31-1-1 8 8-1-110109 98 87 76 65 54 43 32 21 10 045457 72020-1-16 6 -1-11 1-1-11717 -1-13737 -1-12 2-1-123231010 6666 -1-1关键词序列为：关键词序列为：20,17,2,23,45,66,6,

106、37,1杂凑函数：杂凑函数：h(k)=K%11冲突调节：拉链法冲突调节：拉链法 -1-1 -1-1 135数据结构国家精品课程2024/7/31算法算法C(TABLE，K，M.)/*对给定变元对给定变元K，本算法检索，本算法检索M个结点的表。若个结点的表。若K不在表中且表不在表中且表不满，则把不满，则把K插入表中。插入表中。本算法使用了一个散列函数本算法使用了一个散列函数h(K).R是是一个辅助变量，用于找到空的空间；一个辅助变量，用于找到空的空间；R有初始值，有初始值，R=M+1.*/C1.散列散列置置ih(K)+1（现在（现在1 i M，为检索，为检索K，取，取K的散列的散列位置位置i=h

107、(K)+1，去检索，去检索TABLEi).C2.有链表吗有链表吗?若若TABLEi为空，则转到步骤为空，则转到步骤C6.C3.比较比较若若K=KEYi，则本算法以成功告终，则本算法以成功告终.C4.查下一个查下一个若若LINKi ，则置，则置iLINKi并返回步骤并返回步骤C3.136数据结构国家精品课程2024/7/31C5.找找空空结结点点(已已查查完完由由TABLEh(K)+1开开始始的的链链表表，检检索索不不成成功功，故故应应该该插插入入K，所所以以需需要要在在表表中中找找一一个个空空位位置置)令令R减减1（R初初值值为为M+1），进进行行此此操操作作一一次次或或多多次次直直到到TAB

108、LER是是空空为为止止若若R=0（表表明明已已经经没没有有剩剩余余的的空空结结点点），则则本本算算法法以以溢出告终；否则，置溢出告终；否则，置LINKiR，iR.C6.插插入入K标标记记TABLEi为为已已占占用用，置置KEYiK，LINKi，算法以插入成功告终。，算法以插入成功告终。137数据结构国家精品课程2024/7/312.线性探查线性探查线性探查完全废除链接，以固定的次序检索表中线性探查完全废除链接，以固定的次序检索表中的结点，直到找到一个关键词为的结点，直到找到一个关键词为K的结点或者找到的结点或者找到一个空缺位置一个空缺位置.其循环探查路径：其循环探查路径：h(K)，h(K)+1

109、，M-1，0，1，h(K)-1138数据结构国家精品课程2024/7/31109876543210206171374522366关键词序列为：关键词序列为：20,17,2,23,45,66,6,37,1散列函数：散列函数：h(k)=K%11冲突调节：线性探查冲突调节：线性探查139数据结构国家精品课程2024/7/31线性探查查找和插入算法线性探查查找和插入算法L(TABLE，K，M.)/*在一个包含在一个包含M个结点的表中查找一个给定的关键词个结点的表中查找一个给定的关键词K.如果如果K 不在表中且表不满，则插入不在表中且表不满，则插入K变量变量N记录已占用的结点数记录已占用的结点数*/L1

110、.散列散列置置ih(K)./有有0 i ML2.比较比较若若TABLEi为空，则转为空，则转L4；/*去插入去插入K */否则，若否则，若KEYi=K，则本算法以检索成功结束，则本算法以检索成功结束.L3.查下一个查下一个置置ii 1；若；若i M,则置则置i i M返回返回L2.L4.插入插入K若若N=M 1，则本算法以溢出告终，则本算法以溢出告终/*L在在N=M 1就认为表就认为表已经满了已经满了,这样做的结果使得表中永远有一个结点为空这样做的结果使得表中永远有一个结点为空*/；否则否则,置置NN+1,并置并置KEYiK. /*注意在调用注意在调用L的外层算法中，对变量的外层算法中，对变量

111、N初始化初始化*/140数据结构国家精品课程2024/7/313.双重散列双重散列 从从h(K)开开始始，寻寻找找空空地地址址时时，所所前前进进的的步步长长不不是是固固定定的的，而而与与K有有关关，即即用用，1M（是是K的的函函数数），代代替替线线性性探探查查的的前前进进步步长长1。为为了了确确保保表表中中的的每每一一个个地地址址都都能能探探查查到到，必必须须要要求求和和M互互质质，另另外外，还还希希望望与与K有有关关，因因而而可可用用另另一一个个杂杂凑凑函函数数(K)来来代代替替，1(K)M，因因对对任任意意的的K，=(K)都都要要与与M互互质，因此质，因此M应选作质数。应选作质数。141数

112、据结构国家精品课程2024/7/31算法算法D(TABLE，K，M.)/*本算法使用两个散列函数本算法使用两个散列函数h1(K)和和h2(K)对表进行探查。对表进行探查。h1的值域是：的值域是：0 h1(K) M；而；而h 2的值必须是一个与的值必须是一个与M互质的并属于区间互质的并属于区间1，M-1的整数的整数*/D1.第一次散列第一次散列置置ih1(K)D2.第一次探查第一次探查若若TABLEi为空，则转到步骤为空，则转到步骤D6否则若否则若KEYi=K，则本算法以成功告终。，则本算法以成功告终。D3.第二次散列第二次散列置置c h2(K)D4.查下一个查下一个置置i(i +c)modMD

113、5.比较比较若若TABLEi为空，则转为空，则转D6否则若否则若KEYi=K，则，则本算法以成功告终。否则转本算法以成功告终。否则转D4D6.插入插入K若若N=M-1，则本算法由于溢出而中止，否则置，则本算法由于溢出而中止，否则置NN+1标记标记TABLEi为已占用，并置为已占用，并置KEYiK142数据结构国家精品课程2024/7/31一、线性表的查找一、线性表的查找8.1.1无序表的顺序查找无序表的顺序查找8.1.2有序表的顺序查找有序表的顺序查找8.2.1对半查找对半查找8.2.2一致对半查找一致对半查找8.2.3斐波那契查找斐波那契查找8.2.4插值查找插值查找二、树形结构的查找二、树

114、形结构的查找8.3二叉查找树二叉查找树8.5高度平衡树高度平衡树8.7B树及其变型树及其变型三、散列三、散列8.9.1散列表散列表(杂凑表杂凑表)的定义的定义8.9.2散列函数的构造散列函数的构造8.9.3冲突调解冲突调解143数据结构国家精品课程2024/7/31本章作业本章作业l354页：页：8-8、8-10、8-13、8-22144数据结构国家精品课程2024/7/311.有数据有数据53，30，37，12，45，24，96，从空二叉树开始逐，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高度最小，则应选择下个插入数据来形成二叉查找树，若希望高度最小，则应选择下面哪个序列输入面哪个序

115、列输入_。A45,24,53,12,37,96,30B37,24,12,30,53,45,96C12,24,30,37,45,53,96D30,24,12,37,45,96,532.二二叉叉查查找找树树T中中关关键键词词互互异异，则则T的的最最小小关关键键词词必必无无左左孩孩子子（指指内内结结点点），最最大大关关键键词词必必无无右右孩孩子子（指指内内结结点点）。此此命命题题是是否否正正确确?最最小小和和最最大大关关键键词词是是叶叶结结点点吗吗?一一个个新新结结点点（其其关关键键词词不不同同于于T的的任任意意结结点点的的关关键键词词）总总是是作作为为叶叶结结点点被被插插在在二二叉查找树的合适的外

116、结点处吗叉查找树的合适的外结点处吗?本章练习本章练习145数据结构国家精品课程2024/7/313.设设有有序序顺顺序序表表为为10,20,30,40,50,60,70,80，采采用用折折半半查查找找时，查找成功的平均查找长度是多少（各个关键词等概率）？时，查找成功的平均查找长度是多少（各个关键词等概率）？4.试写一个判别给定二叉树是否为二叉查找树的算法。试写一个判别给定二叉树是否为二叉查找树的算法。5.试试给给出出对对有有序序表表进进行行顺顺序序查查找找的的算算法法，并并画画出出关关于于有有序序表表顺顺序序查查找找的的判判定定树树，假假设设每每次次给给定定随随机机的的查查找找值值，且且成成功

117、功和和不不成成功功查查找找之之概概率率相相等等，试试求求进进行行每每一一次次查查找找时时，与与给给定定值值进进行行比比较的关键词个数的期望值。较的关键词个数的期望值。146数据结构国家精品课程2024/7/316.下下图图所所示示的的高高度度平平衡衡二二叉叉树树（AVL树树）中中，依依次次插插入入关关键键词词为为6和和10的两个结点，请分别画出依次插入后的的两个结点，请分别画出依次插入后的AVL树。树。920832147数据结构国家精品课程2024/7/313.答答案案：画画出出相相应应的的二二叉叉判判定定树树，计计算算查查找找成成功功的的平平均均查找次数（查找长度）。查找次数（查找长度）。3010204070608050l查找成功的平均比较次数是查找成功的平均比较次数是(1+2+2+3+3+3+3+4)/8=21/8，l查找失败的平均比较次数是。查找失败的平均比较次数是。(3+3+3+3+3+3+3+4+4)/9=29/9148数据结构国家精品课程2024/7/319208326920836289362208103622098936220106. 答案：答案：