数据结构与算法分析第八章查找.ppt

《数据结构与算法分析第八章查找.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析第八章查找.ppt（151页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Chapter 8Search 所谓搜索所谓搜索(查找查找 检索检索)，就是在数据，就是在数据集合中寻找满足某种条件的数据对象集合中寻找满足某种条件的数据对象 1.搜索成功搜索成功 即找到满足条件的数据即找到满足条件的数据 对象对象,作为结果作为结果,可报告该对象在可报告该对象在 结构中的位置结构中的位置,还可给出该对象中还可给出该对象中 的具体信息的具体信息2.搜索不成功搜索不成功 或搜索失败。作为结或搜索失败。作为结 果果,应报告一些信息应报告一些信息,如失败标如失败标 志、位置等志、位置等 n n通常称用于搜索的数据集合为搜索结通常称用于搜索的数据集合为搜索结构，它是由同一数据类型的对象

2、构，它是由同一数据类型的对象(或记或记录录)组成组成n n在每个对象中有若干属性，其中有一在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。个属性，其值可唯一地标识这个对象。称为关键码。称为关键码。使用基于关键码的搜索，使用基于关键码的搜索，搜索结果应是唯一的。搜索结果应是唯一的。但在实际应用但在实际应用时，搜索条件是多方面的，可以使用时，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可基于属性的搜索方法，但搜索结果可能不唯一能不唯一实施搜索时有两种不同的环境实施搜索时有两种不同的环境n n静态环境静态环境 搜索结构在插入和删除等搜索结构在插入和删除等操作的前后不发

3、生改变操作的前后不发生改变 静态搜索表静态搜索表 n n动态环境动态环境 为保持较高的搜索效率为保持较高的搜索效率,搜索结构在执行插入和删除等操作的搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生前后将自动进行调整，结构可能发生变化变化 动态搜索表动态搜索表查找算法的评价指标查找算法的评价指标 查找成功查找成功:最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数 查找失败查找失败:最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数 以顺序表或线性链以顺序表或线性链表表示静态查找表表表示静态查找表顺序查找顺序查找ST.elem顺

4、序查找过程顺序查找过程假设给定值假设给定值 e=64,要求要求 ST.elemk=e,问问:k=?kkST.elemiST.elemi60ikey=64key=60i64int Search_Seq(TB ST,TYPE key)ST.elem0.key=key;/“哨兵哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找从后往前找 return i;/找不到时，找不到时，i为为0分析顺序查找的分析顺序查找的时间性能时间性能查找算法的平均查找长度查找算法的平均查找长度(Average Search Length)为确定记录在查找表中的位置，需为确定记录

5、在查找表中的位置，需和给定值进行比较的关键字个数的期望和给定值进行比较的关键字个数的期望值值其中其中:n 为表长，为表长，Pi 为查找表中为查找表中第第i个记录的概率，且个记录的概率，且 ，Ci为找到该记录时，曾和给定值为找到该记录时，曾和给定值比较过的关键字的个数比较过的关键字的个数在等概率情形在等概率情形pi=1/n,i=1,2,n 在搜索不成功情形，在搜索不成功情形，ASLunsucc=n+1 查找成功查找成功:最少比较次数最少比较次数 1 1 最多比较次数最多比较次数 n n 平均比较次数平均比较次数(n+1)/2(n+1)/2 查找失败查找失败:最少比较次数最少比较次数 n+1 n+

6、1 最多比较次数最多比较次数 n+1 n+1 平均比较次数平均比较次数 n+1 n+1 上述顺序查找表的查找算法简单，上述顺序查找表的查找算法简单，但平均查找长度较大，特别不但平均查找长度较大，特别不适用于表长较大的查找表适用于表长较大的查找表折半查找折半查找 若以有序表表示静态查找表，若以有序表表示静态查找表，则查找过程可以基于则查找过程可以基于“折半折半”进行进行基于有序顺序表的折半搜索基于有序顺序表的折半搜索n n设设n个个对对象象存存放放在在一一个个有有序序顺顺序序表表中中，并按其关键码从小到大排好了序并按其关键码从小到大排好了序n n折折半半搜搜索索时时,先先求求位位于于搜搜索索区区

7、间间正正中中的的对对象象的的下下标标mid，用用其其关关键键码码与与给给定定值值x比较比较1.Elementmid.key=x 搜索成功搜索成功2.Elementmid.keyx 把把搜搜索索区区间间缩缩小小到表的到表的前半部分前半部分，继续折半搜索，继续折半搜索3.Elementmid.keyx 把把搜搜索索区区间间缩缩小小到表的到表的后半部分后半部分，继续折半搜索，继续折半搜索n n如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未找到想要搜索的对象，则搜索失败未找到想要搜索的对象，则搜索失败ST.elemST.length例如例如:key=64 的查找过程如下mid=(lo

8、w+high)/2Low 指示查找区间的下界指示查找区间的下界high 指示查找区间的上界指示查找区间的上界搜索成功的例子搜索成功的例子-1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜索搜索搜索搜索lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6搜索失败的例子搜索失败的例子-1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8搜索搜索搜索搜索lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5int Search_Bin(T

9、B ST,TYPE key)low=1;high=ST.length;while(low=high)mid=(low+high)/2;if(key=ST.elemmid.key)return mid;if(keyST.elemmid.key)low=mid+1;return 0;uu搜索成功时检测指针停留在树中某个搜索成功时检测指针停留在树中某个结点结点uu搜索不成功时检测指针停留在某个外搜索不成功时检测指针停留在某个外结点（失败结点）结点（失败结点）3515455025102030搜索搜索22搜索搜索45有序顺序表的折半搜索的判定树有序顺序表的折半搜索的判定树(10,20,30,40,50,

10、60)1050=30204060先看一个具体的情况，假设：先看一个具体的情况，假设：n=11分析折半查找的平均查找长度分析折半查找的平均查找长度6391425781011判定树判定树12233334444查找成功查找成功:最少比较次数最少比较次数?最多比较次数最多比较次数?平均比较次数平均比较次数?查找失败查找失败:最少比较次数最少比较次数?最多比较次数最多比较次数?平均比较次数平均比较次数?假设假设 n=2h-1 并且查找概率相等并且查找概率相等则则 在在n50时，可得近似结果时，可得近似结果 一般情况下，表长为一般情况下，表长为 n 的折半查找的折半查找的判定树的深度和含有的判定树的深度和

11、含有 n 个结点的完全个结点的完全二叉树的深度相同二叉树的深度相同索引顺序查找索引顺序查找1）由索引确定记录所在区间）由索引确定记录所在区间2）在顺序表的某个区间内进行查找）在顺序表的某个区间内进行查找注意：索引可以根据查找表的特点来构造注意：索引可以根据查找表的特点来构造可见可见:索引顺序查找的过程也是一个索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程的查找过程 分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现u用数组存放待查记录,每个数据元素至少含有关键字域u建立索引表，每个索引表结点含有最大关键字域和指向本块第一

12、个结点的指针1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38分块查找方法评价索引顺序查找的平均查找长度索引顺序查找的平均查找长度=查找查找“索引索引”的平均查找长度的平均查找长度 +查找查找“顺序表顺序表”的平均查找长度的平均查找长度ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找二叉排序树二叉排序树（二叉

13、查找树）（二叉查找树）（1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值所有结点的值均小于根结点的值 二叉排序树或者是一棵空树；或者二叉排序树或者是一棵空树；或者是具有如下特性的二叉树是具有如下特性的二叉树（3）它的左、右子树也都分别是二叉）它的左、右子树也都分别是二叉 排序树排序树（2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值所有结点的值均大于根结点的值503080209010854035252388是二叉排序树是二叉排序树66不不二叉排序树的二叉排序树的查找算法查找算法 1）若给定值等于根结点的关键

14、字，）若给定值等于根结点的关键字，则查找成功则查找成功 2）若给定值小于根结点的关键字，）若给定值小于根结点的关键字，则继续在左子树上进行查找则继续在左子树上进行查找 3）若给定值大于根结点的关键字，）若给定值大于根结点的关键字，则继续在右子树上进行查找则继续在右子树上进行查找否则否则:若二叉排序树为空，则查找不成功若二叉排序树为空，则查找不成功50308020908540358832查找关键字查找关键字50505030403550508090=50,35,90,95n 个结点的二叉搜索树的数目个结点的二叉搜索树的数目3 个结点的二叉搜索树个结点的二叉搜索树122133132123123123

15、 132 213 231 312 321 如果对一棵二叉搜索树进行中序如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉结点关键码排列起来，所以也称二叉搜索树为二叉排序树搜索树为二叉排序树在查找过程中，生成了一条查找路径在查找过程中，生成了一条查找路径 从根结点出发，沿着左分支或右分从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结支逐层向下直至关键字等于给定值的结点点或者或者从根结点出发，沿着左分支或右分从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止支逐层向下直至指针指向空树为止 查找成功查

16、找成功 查找不成功查找不成功351545504025102030搜索搜索45 搜索成功搜索成功 搜索搜索28搜索失败搜索失败查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它均可按照平均查找长度的定义来求它的的 ASL 值，显然，由值相同的值，显然，由值相同的 n个关个关键字，构造所得的不同形态的各棵二键字，构造所得的不同形态的各棵二叉排序树的平均查找长叉排序树的平均查找长 度的值不同，度的值不同，甚至可能差别很大甚至可能差别很大由关键字序列由关键字序列 3，1，2，5，4构造而得的二叉排序树构造而得的二叉排序树由关键字序列由

17、关键字序列 1，2，3，4，5构造而得的二叉排序树构造而得的二叉排序树2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2 输入数据，建立二叉搜索树的过程输入数据，建立二叉搜索树的过程输入数据输入数据 53,78,65,17,87,09,81,15 535378537865537865175378658717537865091787537865811787095378651517870981 同样同样 3 个数据个数据 1,2,3，输入顺序，输入顺序不同，建立起来的二叉搜索树的形态也不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的

18、搜索不同。这直接影响到二叉搜索树的搜索性能性能 如果输入序列选得不好，会建立起如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达一棵单支树，使得二叉搜索树的高度达到最大到最大 2,1,31,2,3 1,3,2 2,3,1 3,1,2 3,2,1123111132223323二叉平衡树二叉平衡树（AVLAVL树树）一棵一棵AVL树或者是空树，或者是具树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树有下列性质的二叉搜索树：它的左子树和右子树都是和右子树都是AVL树，且左子树和右子树，且左子树和右子树的高度之差的绝对值不超过树的高度之差的绝对值不超过1 不平衡不平衡 平衡平衡A

19、BCABCDEDE 结点的平衡因子结点的平衡因子(balance factor)每个结点附加一个数字每个结点附加一个数字,给出该给出该结点右子树的高度减去左子树的高度结点右子树的高度减去左子树的高度所得的高度差所得的高度差,这个数字即为结点的这个数字即为结点的平衡因子平衡因子AVL树任一结点平衡因子只能取树任一结点平衡因子只能取-1,0,1n n如果一个结点的平衡因子的绝对如果一个结点的平衡因子的绝对值大于值大于1,则这棵二叉搜索树就失则这棵二叉搜索树就失去了平衡去了平衡,不再是不再是AVL树树n n如果一棵二叉搜索树是平衡的如果一棵二叉搜索树是平衡的,且有且有 n个结点，其高度可保持在个结点

20、，其高度可保持在 O(log2n),平均搜索长度也可保持平均搜索长度也可保持在在O(log2n)548254821是平衡树是平衡树不是平衡树不是平衡树平衡化旋转平衡化旋转n n如果在一棵平衡的二叉搜索树中插入如果在一棵平衡的二叉搜索树中插入一个新结点，造成了不平衡。此时必一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化须调整树的结构，使之平衡化n n平衡化旋转有两类：平衡化旋转有两类：uu 单旋转单旋转(左旋和右旋左旋和右旋)uu 双旋转双旋转(左旋加右旋和右旋加左旋左旋加右旋和右旋加左旋)n n每插入一个新结点时每插入一个新结点时,AVL 树中相关树中相关 结点的平衡状态会发生改变

21、。因此结点的平衡状态会发生改变。因此,在插入一在插入一 个新结点后，需要个新结点后，需要从插入位从插入位置沿通向根的路径回溯置沿通向根的路径回溯，检查各结点检查各结点的平衡因子的平衡因子n n如果在某一结点发现高度不平衡，停如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点刚才回溯的路径取直接下两层的结点如果这三个结点处于一条直线上，则采用单如果这三个结点处于一条直线上，则采用单旋转进行平衡化旋转进行平衡化 单旋转可按其方向分为单旋转可按其方向分为左单旋转和右单旋转左单旋转和右单旋转,其中一个是另一其中一个是另一 个

22、个的镜像的镜像,其方向与不平衡的形状相关其方向与不平衡的形状相关如果这三个结点处于一条折线上，则采用双如果这三个结点处于一条折线上，则采用双旋转进行平衡化旋转进行平衡化 双旋转分为先左后右和双旋转分为先左后右和先右后左两类先右后左两类右单旋转右单旋转R型型左单旋转左单旋转L型型左右双旋转左右双旋转LR型型右左双旋转右左双旋转RL型型左单旋转左单旋转(RotateLeft,L型型)hhhACEBDhhh+1BACEDhhh+1CEABD+1+1+2+20 0+1+10 00 0 在子树在子树E中插入新结点，该子树中插入新结点，该子树 高度增高度增 1导致结点导致结点 A的平衡因子的平衡因子 变成

23、变成 +2，产生不平衡，产生不平衡(L型型)以结点以结点C为旋转轴，将结点为旋转轴，将结点A反时针旋转反时针旋转右单旋转右单旋转(RotateRight,R型型)在子树在子树D中插入新结点中插入新结点,该子树该子树 高度增高度增 1导致结点导致结点 A的平衡因子的平衡因子 变成变成 -2，产生不平衡，产生不平衡(R型型)以结点以结点B为旋转轴，将结点为旋转轴，将结点A顺时针旋转顺时针旋转hhhACEBDhh+1BACEDhhh+1CEABDh0 00 00 0-1 1-1 1-2 2先左后右双旋转先左后右双旋转(RotationLeftRight,LR型型)在子树在子树F或或G中插入新结点，该

24、子树中插入新结点，该子树高度增高度增 1 导致结点导致结点 A 的平衡因子变成的平衡因子变成-2，产生不平衡，产生不平衡(LR型型)n n首首先先以以结结点点E为为旋旋转转轴轴，将将结结点点B反反时时针针旋旋转转，以以E代代替替原原来来B的的位位置置，做做左左单旋转单旋转n n再再以以结结点点E为为旋旋转转轴轴，将将结结点点A顺顺时时针针旋转，做右单旋转旋转，做右单旋转插入插入0 00 0-1 1-2 2+1+1-1 1hhACED0 0 0 0h-1h-1hhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转FGFG0 00 0-2 20 0 0 00 0+1+1hhACED-2 2h-1

25、hhhAh-1hBCEDB右单右单右单右单旋转旋转旋转旋转FGFG先右后左双旋转先右后左双旋转(RotationRightLeft,RL型型)在子树在子树F或或G中插入新结点，该子树中插入新结点，该子树高度增高度增 1 导致结点导致结点 A 的平衡因子变成的平衡因子变成2，产生不平衡，产生不平衡(RL型型)n n首首先先以以结结点点D为为旋旋转转轴轴，将将结结点点C顺顺时时针针旋旋转转，以以D代代替替原原来来C的的位位置置,做做右右单单旋转旋转n n再再以以结结点点D为为旋旋转转轴轴，将将结结点点A反反时时针针旋转，做左单旋转旋转，做左单旋转插入插入插入插入右右右右单单单单旋旋旋旋转转转转+1

26、+10 00 00 0-1 1+1+10 0hhACEDh-1BFGh-1+2+20 00 00 0hhACEhBFGh-1D0 00 0+2+20 0 0 0-1 10 0hhACE+2 2h-1hhhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转FGFGD构造二叉平衡（查找）树的方法构造二叉平衡（查找）树的方法在插入过程中，采用平衡旋转技术在插入过程中，采用平衡旋转技术依次插入的关键字为依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转426589642895向左旋转一次继续插入关键字继续插入关键字 9输入关键码序列为输入关键码序列为

27、16,3,7,11,9,26,18,14,15 插入和调整过程如下插入和调整过程如下16160 03163-1 10 07 70 01 1-2 2左右双旋左右双旋7 73160 00 00 07 73110 0-1 11 1161 12 22 27 73161190 0-1 1-2 2右单旋右单旋37 71690 00 00 037 71126916110 01 11 12 2 2 2右左双旋右左双旋左单左单18183-1 1160 00 00 0732611-1 19716140 00 02691 1110 03160 02 27390 0182611-1 11691 1711261 115

28、182 231816-2 2左右双旋左右双旋730 00 00 0117149-1 116150 01 1112626141 1-2 29从空树开始的建树过程从空树开始的建树过程B 树树大型文件访问方法大型文件访问方法B树是一种树是一种 平衡平衡 的的 多路多路 查找查找 树树 在在 m 阶的阶的B树上，每个非终端结点树上，每个非终端结点可能含有：可能含有：n 个关键字个关键字 Ki（1 in）nm n 个指向记录的指针个指向记录的指针 Di（1in）n+1 个指向子树的指针个指向子树的指针 Ai（0in）多叉树的特性多叉树的特性 非叶结点中的多个关键字均自小至大有非叶结点中的多个关键字均自小

29、至大有序排列，即：序排列，即：K1 K2 Kn Ai-1 所指子树上所有关键字均小于所指子树上所有关键字均小于Ki Ai 所指子树上所有关键字均大于所指子树上所有关键字均大于Ki查找树的特性查找树的特性平衡树的特性平衡树的特性 树中所有叶子结点均不带信息，且在树树中所有叶子结点均不带信息，且在树中的同一层次上中的同一层次上 根结点或为叶子结点，或至少含有两棵根结点或为叶子结点，或至少含有两棵子树子树 其余所有非叶结点均至少含有其余所有非叶结点均至少含有 m/2 棵棵子树，至多含有子树，至多含有 m 棵子树棵子树 从根结点出发，沿指针搜索结点和从根结点出发，沿指针搜索结点和在结点内进行顺序（或折

30、半）查找在结点内进行顺序（或折半）查找 两个两个过程交叉进行过程交叉进行查找过程查找过程 若查找成功，则返回指向被查关键若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的字所在结点的指针和关键字在结点中的位置位置 若查找不成功，则返回插入位置若查找不成功，则返回插入位置 在查找不成功之后，需进行插入在查找不成功之后，需进行插入 显然，关键字插入的位置必定在最显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况下层的非叶结点，有下列几种情况插插 入入插入后，该结点的关键字个数插入后，该结点的关键字个数nm，不修改指针不修改指针插入后，该结点的关键字个数插入后，该结点的关键字

31、个数 n=m，则需进行则需进行“结点分裂结点分裂”，令，令 s=m/2，在原结点中保留在原结点中保留 （A0，K1，Ks-1，As-1）；）；建新结点建新结点 （As，Ks+1，Kn，An）；）；将（将（Ks，p）插入双亲结点）插入双亲结点若双亲为空，则建新的根结点若双亲为空，则建新的根结点下列为下列为 3 阶阶B树树50 20 40 80 插入关键字插入关键字=60 60 80 ,90 60 80 90 90 50 80 60,30 40 20 30 50 8030 5080 和插入的考虑相反，首先必须找到待删和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点关键字所在

32、结点，并且要求删除之后，结点中关键字的个数不能小于中关键字的个数不能小于 m/2-1，否则，要，否则，要从其左从其左(或右或右)兄弟结点兄弟结点“借调借调”关键字，若关键字，若其左和右兄弟结点均无关键字可借其左和右兄弟结点均无关键字可借(结点中只结点中只有最少量的关键字有最少量的关键字)，则必须进行结点的，则必须进行结点的“合合并并”删删 除除 在含在含 N 个关键字的个关键字的 B树上树上进行一次查找，需访问的结点个进行一次查找，需访问的结点个数不超过数不超过 log m/2(N+1)/2)+1查找性能查找性能是是B树的一种变型树的一种变型B+树树 每个叶子结点中含有每个叶子结点中含有 n

33、个关键个关键字和字和 n 个指向记录的指针；并且，个指向记录的指针；并且，所有叶子结点彼此相链接构成一个所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关有序链表，其头指针指向含最小关键字的结点键字的结点 每个非叶结点中的关键字每个非叶结点中的关键字 Ki 即即为其相应指针为其相应指针 Ai 所指子树中关键字所指子树中关键字的最大值的最大值 所有叶子结点都处在同一层次所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数上，每个叶子结点中关键字的个数均介于均介于 m/2 和和 m 之间之间查找过程查找过程 在在 B+树上，既可以进行缩小范围树上，既可以进行缩小范围的查找，也可以进行

34、顺序查找的查找，也可以进行顺序查找 在进行缩小范围的查找时，不管成在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结功与否，都必须查到叶子结点才能结束束 若在结点内查找时，给定值若在结点内查找时，给定值Ki，则则应继续在应继续在 Ai 所指子树中进行查找所指子树中进行查找插入和删除插入和删除类似于类似于B树进行，即必要时，树进行，即必要时，也需要进行结点的也需要进行结点的“分裂分裂”或或“归并归并”50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot B+树的删除仅在叶结点上进行。当在叶结点上树的删除仅在叶结

35、点上进行。当在叶结点上删除一个关键码删除一个关键码-指针索引项后，结点中的子树指针索引项后，结点中的子树棵数仍然不少于棵数仍然不少于 m/2，这属于简单删除，其上，这属于简单删除，其上层索引可以不改变。层索引可以不改变。如果删除的关键码是该结点的最小关键码，但如果删除的关键码是该结点的最小关键码，但因在其上层的副本只是起了一个引导搜索的因在其上层的副本只是起了一个引导搜索的“分界关键码分界关键码”的作用，所以上层的副本仍然可的作用，所以上层的副本仍然可以保留。以保留。如果在叶结点中删除一个关键码如果在叶结点中删除一个关键码-指针索引项后，指针索引项后，该结点中的子树棵数该结点中的子树棵数 n

36、小于结点子树棵数的下小于结点子树棵数的下限限 m/2，必须做结点的调整或合并工作。，必须做结点的调整或合并工作。删除删除18删除删除12 如如果果右右兄兄弟弟结结点点的的子子树树棵棵数数已已达达到到下下限限 m/2，没没有有多多余余的的关关键键码码可可以以移移入入被被删删关关键键码码所所在在的的结结点点，这这时时必必须须进进行行两两个个结结点点的的合合并并。将将右右兄兄弟弟结结点点中中的的所所有有关关键键码码-指指针针索索引引项项移移入入被被删删关键码所在结点，再将右兄弟结点删去。关键码所在结点，再将右兄弟结点删去。删除删除33进行进行结点合并结点合并 结结点点的的合合并并将将导导致致双双亲亲

37、结结点点中中“分分界界关关键键码码”的的减减少少，有有可可能能减减到到非非叶叶结结点点中中子子树树棵棵数数的的下下限限 m/2 以以下下。这这样样将将引引起起非非叶叶结结点点的调整或合并。的调整或合并。如如果果根根结结点点的的最最后后两两个个子子女女结结点点合合并并，树树的的层数就会减少一层。层数就会减少一层。The B*-Tree splits two pages for three,and combines three pages into two.In this way,nodes are always 2/3 full.Trie树是一棵度树是一棵度 m 2 的树，它的每一层分支不的树，

38、它的每一层分支不是靠整个关键码的值来确定，而是由关键码的是靠整个关键码的值来确定，而是由关键码的一个分量来确定。一个分量来确定。如下图所示如下图所示Trie树，关键码由英文字母组成。它树，关键码由英文字母组成。它包括两类结点：元素结点和分支结点。元素结包括两类结点：元素结点和分支结点。元素结点包含整个点包含整个key数据；分支结点有数据；分支结点有27个指针，其个指针，其中有一个空白字符中有一个空白字符b，用来终结关键码；其，用来终结关键码；其它用来标识它用来标识a,b,.,z等等26个英个英文字母。文字母。Trie树Trie树的定义树的定义当关键码是可变长时，当关键码是可变长时，Trie树是

39、一种特别有用的树是一种特别有用的索引结构。索引结构。在第在第0层，所有的关键码根据它们第层，所有的关键码根据它们第0位字符位字符,被划分到互不相交的被划分到互不相交的27个类中。个类中。因此，因此，rootbrch.linki 指向一棵子指向一棵子Trie树，该树，该子子Trie树上所包含的所有关键码都是以第树上所包含的所有关键码都是以第 i 个个英文字母开头。英文字母开头。若某一关键码第若某一关键码第 j 位字母在英文字母表中顺序位字母在英文字母表中顺序为为 i (i=0,1,26),则它在则它在Trie树的第树的第 j 层层分支结点中从第分支结点中从第 i 个指针向下找第个指针向下找第 j

40、+1 位字母位字母所在结点。当一棵子所在结点。当一棵子Trie树上只有一个关键码树上只有一个关键码时，就由一个元素结点来代替。在这个结点中时，就由一个元素结点来代替。在这个结点中包含有关键码，以及其它相关的信息，如对应包含有关键码，以及其它相关的信息，如对应数据对象的存放地址等。数据对象的存放地址等。Trie树的搜索树的搜索 为了在为了在Trie树上进行搜索，要求把关键码树上进行搜索，要求把关键码分解成一些字符元素分解成一些字符元素,并根据这些字符并根据这些字符向下进行分支。向下进行分支。在在Trie树上插入树上插入bobwhite和和bluejay后的结果后的结果哈哈 希希 查查 找找(Ha

41、sh)以上讨论的表示查找表的各种以上讨论的表示查找表的各种结构的共同特点：记录在表中的位结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确置和它的关键字之间不存在一个确定的关系定的关系 查找的过程为给定值依次和关查找的过程为给定值依次和关键字集合中各个关键字进行比较键字集合中各个关键字进行比较 查找的效率取决于和给定值进查找的效率取决于和给定值进行比较的关键字个数行比较的关键字个数 用这类方法表示的查找表，用这类方法表示的查找表，其平均查找长度都不为零其平均查找长度都不为零 不同的表示方法，其差别仅在不同的表示方法，其差别仅在于：于：关键字和给定值进行比较的顺关键字和给定值进行比较的

42、顺序不同序不同 只有一个办法：预先知道所查关只有一个办法：预先知道所查关键字在表中的位置键字在表中的位置对于频繁使用的查找表，希望对于频繁使用的查找表，希望ASL=0 即，要求：记录在表中位置和其即，要求：记录在表中位置和其关键字之间存在一种确定的关系关键字之间存在一种确定的关系 在一般情况下，需在关键字与记在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函录在表中的存储位置之间建立一个函数关系，以数关系，以 H(key)作为关键字为作为关键字为 key 的记录在表中的位置，通常称这的记录在表中的位置，通常称这个函数个函数 H(key)为哈希函数为哈希函数 哈希函数是一个映象，即：哈

43、希函数是一个映象，即：将关键将关键 字的集合映射到某个地址字的集合映射到某个地址集合上，它集合上，它 的设置很灵活，只要的设置很灵活，只要这个地址集合的这个地址集合的 大小不超出允许大小不超出允许范围即可范围即可 由于哈希函数是一个压缩由于哈希函数是一个压缩映象，因映象，因 此，在一般情况，很此，在一般情况，很容易产生容易产生“冲冲 突突”现象，即：现象，即：key1 key2，而，而 H(key1)=H(key2)很难找到一个不产生冲突的哈希很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生哈希函数，使冲突尽可能少地产生

44、 因此，在构造这种特殊的因此，在构造这种特殊的“查查找表找表”时，除了需要选择一个时，除了需要选择一个“好好”(尽可能少产生冲突尽可能少产生冲突)的哈希函数的哈希函数之外；还需要找到一种之外；还需要找到一种“处理冲突处理冲突”的方法的方法哈希表的定义哈希表的定义 根据设定的哈希函数根据设定的哈希函数 H(key)和所和所选处理冲突的方法，将一组关键字映象选处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集到一个有限的、地址连续的地址集(区区间间)上，并以关键字在地址集中的上，并以关键字在地址集中的“映映象象”作为相应记录在表中的存储位置，作为相应记录在表中的存储位置，如此构造所得的

45、查找表称为如此构造所得的查找表称为“哈希表哈希表”构造哈希函数的方法构造哈希函数的方法对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法 若是非数字关键字，则需先对若是非数字关键字，则需先对其进行数字化处理其进行数字化处理 直接定址法直接定址法 平方取中法平方取中法 除留余数法除留余数法 折叠法折叠法 数字分析法数字分析法数字分析法数字分析法 此方法适合于：此方法适合于：能预先估计出全体关键字的每一位能预先估计出全体关键字的每一位 上各种数字出现的频度上各种数字出现的频度 假设关键字集合中的每个关键字都假设关键字集合中的每个关键字都是由是由 s 位数字组成位数字组成(u1,u2,us

46、)，分析，分析关键字集中的全体，关键字集中的全体，并从中提取分布均并从中提取分布均匀的若干位或它们的组合作为地址匀的若干位或它们的组合作为地址平方取中法平方取中法 以关键字的平方值的中间几位作为以关键字的平方值的中间几位作为存储地址。求存储地址。求“关键字的平方值关键字的平方值”的目的目的是的是“扩大差别扩大差别”，同时平方值的中间，同时平方值的中间各位又能受到整个关键字中各位的影响各位又能受到整个关键字中各位的影响 此方法适合于此方法适合于:关键字中的每一位都有某些数字重关键字中的每一位都有某些数字重复出现频度很高的现象复出现频度很高的现象折叠法折叠法 将关键字分割成若干部分，然将关键字分割

47、成若干部分，然后取它们的叠加和为哈希地址。有后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和两种叠加处理的方法：移位叠加和间界叠加间界叠加 此方法适合于此方法适合于:关键字的数字位数特别多关键字的数字位数特别多直接定址法直接定址法哈希函数为关键字的线性函数哈希函数为关键字的线性函数 H(key)=key 或者或者 H(key)=a key+b此法适合于：此法适合于：地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小除留余数法除留余数法 设定哈希函数为设定哈希函数为:H(key)=key MOD p 其中，其中，pm(表长表长)并且并且 p 应为不大于应为不大于 m 的素

48、数的素数 或是或是 不含不含 20 以下的质因子以下的质因子 实际造表时，采用何种构造哈希实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合函数的方法取决于建表的关键字集合的情况的情况(包括关键字的范围和形态包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到总的原则是使产生冲突的可能性降到尽可能地小尽可能地小处理冲突的方法处理冲突的方法“处理冲突处理冲突”的实际含义是的实际含义是为产生冲突的地址寻找下一个哈希地址为产生冲突的地址寻找下一个哈希地址1.开放定址法开放定址法2.链地址法链地址法 为产生冲突的地址为产生冲突的地址 H(key)求得求得一个地址序列：一个地址序列：H0

49、,H1,H2,Hs 1 sm-1其中：其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s开放定址法开放定址法(闭域法闭域法)增量 di 的三种取法 1)线线性性探探测测再再散散列列 di=c i 最简单的情况最简单的情况 c=1 2)平平方方探探测测再再散散列列 di=12,-12,22,-22,3)随随机机探探测测再再散散列列 di 是一组伪随机数列是一组伪随机数列 或者或者 di=iH2(key)(又称双散列函数探测又称双散列函数探测)即：产生的即：产生的 Hi 均不相同，且所产生的均不相同，且所产生的 s(m-1)个个 Hi 值能覆盖哈希表中所值能覆盖哈希表中

50、所 有地址。且要求：有地址。且要求：增量增量 di 应具有应具有“完备性完备性”随机探测时的随机探测时的 m 和和 di 没有公因子没有公因子 平方探测时的表长平方探测时的表长 m 必为形如必为形如 4j+3 的素数（如的素数（如:7,11,19,23,等）等）19,01,23,14,55,68,11,82,36 H(key)=key MOD 11 190123 145568190123 1468若采用线性探测再散列处理冲突若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突若采用二次探测再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 1查找成功查找成功:最少比