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

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

1、数据结构与算法分析第八章查找第1页，本讲稿共151页 所谓搜索所谓搜索(查找查找 检索检索)，就是在数据，就是在数据集合中寻找满足某种条件的数据对象集合中寻找满足某种条件的数据对象 1.搜索成功搜索成功 即找到满足条件的数据即找到满足条件的数据 对象对象,作为结果作为结果,可报告该对象在可报告该对象在 结构中的位置结构中的位置,还可给出该对象中还可给出该对象中 的具体信息的具体信息2.搜索不成功搜索不成功 或搜索失败。作为结或搜索失败。作为结 果果,应报告一些信息应报告一些信息,如失败标如失败标 志、位置等志、位置等 第2页，本讲稿共151页n n通常称用于搜索的数据集合为搜索结构，通常称用于

2、搜索的数据集合为搜索结构，它是由同一数据类型的对象它是由同一数据类型的对象(或记录或记录)组成组成n n在每个对象中有若干属性，其中有一个在每个对象中有若干属性，其中有一个属性，其值可唯一地标识这个对象。称属性，其值可唯一地标识这个对象。称为关键码。为关键码。使用基于关键码的搜索，搜使用基于关键码的搜索，搜索结果应是唯一的。索结果应是唯一的。但在实际应用时，搜但在实际应用时，搜索条件是多方面的，可以使用基于属性的索条件是多方面的，可以使用基于属性的搜索方法，但搜索结果可能不唯一搜索方法，但搜索结果可能不唯一第3页，本讲稿共151页实施搜索时有两种不同的环境实施搜索时有两种不同的环境n n静态环

3、境静态环境 搜索结构在插入和删除等搜索结构在插入和删除等操作的前后不发生改变操作的前后不发生改变 静态搜索表静态搜索表 动态环境动态环境 为保持较高的搜索效率为保持较高的搜索效率,搜索结构在执行插入和删除等操作的搜索结构在执行插入和删除等操作的前后将自动进行调整，结构可能发生前后将自动进行调整，结构可能发生变化变化 动态搜索表动态搜索表第4页，本讲稿共151页查找算法的评价指标查找算法的评价指标 查找成功查找成功:最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数 查找失败查找失败:最少比较次数最少比较次数 最多比较次数最多比较次数 平均比较次数平均比较次数第5页，本

4、讲稿共151页 以顺序表或线性链表表示静态查找表顺序查找第6页，本讲稿共151页ST.elem顺序查找过程顺序查找过程假设给定值假设给定值 e=64,要求要求 ST.elemk=e,问问:k=?kk第7页，本讲稿共151页ST.elemiST.elemi60ikey=64key=60i64第8页，本讲稿共151页int Search_Seq(TB ST,TYPE key)ST.elem0.key=key;/“哨兵哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找从后往前找 return i;/找不到时，找不到时，i为为0第9页，本讲稿共151页分析顺

5、序查找的分析顺序查找的时间性能时间性能第10页，本讲稿共151页查找算法的平均查找长度查找算法的平均查找长度(Average Search Length)为确定记录在查找表中的位置，需为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望和给定值进行比较的关键字个数的期望值值第11页，本讲稿共151页其中其中:n 为表长，为表长，Pi 为查找表中为查找表中第第i个记录的概率，且个记录的概率，且 ，Ci为找到该记录时，曾和给定值为找到该记录时，曾和给定值比较过的关键字的个数比较过的关键字的个数第12页，本讲稿共151页在等概率情形在等概率情形pi=1/n,i=1,2,n 在搜索不成功情

6、形，在搜索不成功情形，ASLunsucc=n+1 第13页，本讲稿共151页查找成功查找成功:最少比较次数最少比较次数 1 1 最多比较次数最多比较次数 n n 平均比较次数平均比较次数 (n+1)/2(n+1)/2 查找失败查找失败:最少比较次数最少比较次数 n+1n+1 最多比较次数最多比较次数 n+1n+1 平均比较次数平均比较次数 n+1n+1第14页，本讲稿共151页 上述顺序查找表的查找算法简单，上述顺序查找表的查找算法简单，但平均查找长度较大，特别不但平均查找长度较大，特别不适用于表长较大的查找表适用于表长较大的查找表折半查找折半查找 若以有序表表示静态查找表，若以有序表表示静态

7、查找表，则查找过程可以基于则查找过程可以基于“折半折半”进行进行第15页，本讲稿共151页基于有序顺序表的折半搜索基于有序顺序表的折半搜索n n设设n个个对对象象存存放放在在一一个个有有序序顺顺序序表表中中，并并按其关键码从小到大排好了序按其关键码从小到大排好了序n n折折半半搜搜索索时时,先先求求位位于于搜搜索索区区间间正正中中的的对对象的下标象的下标mid，用其关键码与给定值，用其关键码与给定值x比较比较第16页，本讲稿共151页1.Elementmid.key=x 搜索成功搜索成功2.Elementmid.keyx 把把搜搜索索区区间间缩缩小小到到表表的的前半部分前半部分，继续折半搜索，

8、继续折半搜索3.Elementmid.keyx 把把搜搜索索区区间间缩缩小小到到表的表的后半部分后半部分，继续折半搜索，继续折半搜索n n如如果果搜搜索索区区间间已已缩缩小小到到一一个个对对象象，仍仍未未找到想要搜索的对象，则搜索失败找到想要搜索的对象，则搜索失败第17页，本讲稿共151页ST.elemST.length例如例如:key=64 的查找过程如下mid=(low+high)/2Low 指示查找区间的下界指示查找区间的下界high 指示查找区间的上界指示查找区间的上界第18页，本讲稿共151页搜索成功的例子-1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8搜

9、索搜索搜索搜索lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6第19页，本讲稿共151页搜索失败的例子-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 high5第20页，本讲稿共151页int Search_Bin(TB ST,TYPE key)low=1;high=ST.length;while(low=high)mid=(low+high)/2;if(key=ST.elemmid.key

10、)return mid;if(keyST.elemmid.key)low=mid+1;return 0;第21页，本讲稿共151页uu搜索成功时检测指针停留在树中某个结点搜索成功时检测指针停留在树中某个结点uu搜索不成功时检测指针停留在某个外结搜索不成功时检测指针停留在某个外结点（失败结点）点（失败结点）3515455025102030搜索搜索22搜索搜索45第22页，本讲稿共151页有序顺序表的折半搜索的判定树有序顺序表的折半搜索的判定树(10,20,30,40,50,60)1050=30204060第23页，本讲稿共151页先看一个具体的情况，假设：先看一个具体的情况，假设：n=11分析折

11、半查找的平均查找长度分析折半查找的平均查找长度6391425781011判定树判定树12233334444第24页，本讲稿共151页查找成功查找成功:最少比较次数最少比较次数?最多比较次数最多比较次数?平均比较次数平均比较次数?查找失败查找失败:最少比较次数最少比较次数?最多比较次数最多比较次数?平均比较次数平均比较次数?第25页，本讲稿共151页假设假设 n=2h-1 并且查找概率相等并且查找概率相等则则 在在n50时，可得近似结果时，可得近似结果 一般情况下，表长为一般情况下，表长为 n 的折半查找的折半查找的判定树的深度和含有的判定树的深度和含有 n 个结点的完全个结点的完全二叉树的深度

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

13、块第一个结点的指针第28页，本讲稿共151页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第29页，本讲稿共151页分块查找方法评价第30页，本讲稿共151页索引顺序查找的平均查找长度索引顺序查找的平均查找长度=查找查找“索引索引”的平均查找长度的平均查找长度 +查找查找“顺序表顺序表”的平均查找长度的平均查找长度第31页，本讲稿共151页ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存

14、储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找第32页，本讲稿共151页二叉排序树（二叉查找树）第33页，本讲稿共151页（1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值所有结点的值均小于根结点的值 二叉排序树或者是一棵空树；或者二叉排序树或者是一棵空树；或者是具有如下特性的二叉树是具有如下特性的二叉树（3）它的左、右子树也都分别是二叉）它的左、右子树也都分别是二叉 排序树排序树（2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值所有结点的值均大于根结点的值第34页，本

15、讲稿共151页503080209010854035252388是二叉排序树是二叉排序树66不不第35页，本讲稿共151页二叉排序树的二叉排序树的查找算法查找算法第36页，本讲稿共151页 1）若给定值等于根结点的关键字，）若给定值等于根结点的关键字，则查找成功则查找成功 2）若给定值小于根结点的关键字，）若给定值小于根结点的关键字，则继续在左子树上进行查找则继续在左子树上进行查找 3）若给定值大于根结点的关键字，）若给定值大于根结点的关键字，则继续在右子树上进行查找则继续在右子树上进行查找否则否则:若二叉排序树为空，则查找不成功若二叉排序树为空，则查找不成功第37页，本讲稿共151页50308

16、020908540358832查找关键字查找关键字50505030403550508090=50,35,90,95第38页，本讲稿共151页n 个结点的二叉搜索树的数目个结点的二叉搜索树的数目3 个结点的二叉搜索树个结点的二叉搜索树122133132123123123 132 213 231 312 321第39页，本讲稿共151页 如果对一棵二叉搜索树进行中序如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉结点关键码排列起来，所以也称二叉搜索树为二叉排序树搜索树为二叉排序树第40页，本讲稿共151页在查找过程中，生成

17、了一条查找路径在查找过程中，生成了一条查找路径 从根结点出发，沿着左分支或右分从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结支逐层向下直至关键字等于给定值的结点点或者或者从根结点出发，沿着左分支或右分从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止支逐层向下直至指针指向空树为止 查找成功查找成功 查找不成功查找不成功第41页，本讲稿共151页351545504025102030搜索搜索45 搜索成功搜索成功 搜索搜索28搜索失败搜索失败第42页，本讲稿共151页查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相

18、同的 n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大第43页，本讲稿共151页由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字序列 1，2，3，4，5构造而得的二叉排序树2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第44页，本讲稿共151页 输入数据，建立二叉搜索树的过程输入数据，建立二叉搜索树的过程输入数据输入数据 53,78,65,17,87,09,81,15 5353785378655378651753786587175378650917875378658117870953786

19、51517870981第45页，本讲稿共151页 同样同样 3 个数据个数据 1,2,3，输入顺序，输入顺序不同，建立起来的二叉搜索树的形态也不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索不同。这直接影响到二叉搜索树的搜索性能性能 如果输入序列选得不好，会建立起如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达一棵单支树，使得二叉搜索树的高度达到最大到最大 第46页，本讲稿共151页2,1,31,2,3 1,3,2 2,3,1 3,1,2 3,2,1123111132223323第47页，本讲稿共151页二叉平衡树二叉平衡树（AVLAVL树树）第48页，本讲

20、稿共151页 一棵一棵AVL树或者是空树，或者是具树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树有下列性质的二叉搜索树：它的左子树和右子树都是和右子树都是AVL树，且左子树和右子树，且左子树和右子树的高度之差的绝对值不超过树的高度之差的绝对值不超过1 不平衡不平衡 平衡平衡ABCABCDEDE第49页，本讲稿共151页 结点的平衡因子结点的平衡因子(balance factor)每个结点附加一个数字每个结点附加一个数字,给出该结给出该结点右子树的高度减去左子树的高度所得点右子树的高度减去左子树的高度所得的高度差的高度差,这个数字即为结点的平衡因子这个数字即为结点的平衡因子AVL树任一

21、结点平衡因子只能取树任一结点平衡因子只能取-1,0,1第50页，本讲稿共151页n n如果一个结点的平衡因子的绝对值如果一个结点的平衡因子的绝对值大于大于1,则这棵二叉搜索树就失去了则这棵二叉搜索树就失去了平衡平衡,不再是不再是AVL树树n n如果一棵二叉搜索树是平衡的如果一棵二叉搜索树是平衡的,且有且有 n个结点，其高度可保持在个结点，其高度可保持在 O(log2n),平均搜索长度也可保持在平均搜索长度也可保持在O(log2n)第51页，本讲稿共151页548254821是平衡树不是平衡树第52页，本讲稿共151页平衡化旋转平衡化旋转n n如果在一棵平衡的二叉搜索树中插入一如果在一棵平衡的二

22、叉搜索树中插入一个新结点，造成了不平衡。此时必须调个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化整树的结构，使之平衡化n n平衡化旋转有两类：平衡化旋转有两类：uu 单旋转单旋转(左旋和右旋左旋和右旋)uu 双旋转双旋转(左旋加右旋和右旋加左旋左旋加右旋和右旋加左旋)第53页，本讲稿共151页n n每插入一个新结点时每插入一个新结点时,AVL 树中相关树中相关 结点的平衡状态会发生改变。因此结点的平衡状态会发生改变。因此,在插在插入一入一 个新结点后，需要个新结点后，需要从插入位置沿通从插入位置沿通向根的路径回溯向根的路径回溯，检查各结点的平衡因检查各结点的平衡因子子第54页，本讲稿

23、共151页n n如果在某一结点发现高度不平衡，停止回如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点的路径取直接下两层的结点第55页，本讲稿共151页如果这三个结点处于一条直线上，则采用单旋如果这三个结点处于一条直线上，则采用单旋转进行平衡化转进行平衡化 单旋转可按其方向分为左单旋单旋转可按其方向分为左单旋转和右单旋转转和右单旋转,其中一个是另一其中一个是另一 个的镜像个的镜像,其其方向与不平衡的形状相关方向与不平衡的形状相关如果这三个结点处于一条折线上，则采用双旋转如果这三个结点处于一条折线上，则采用双旋转进

24、行平衡化进行平衡化 双旋转分为先左后右和先右后左双旋转分为先左后右和先右后左两类两类第56页，本讲稿共151页右单旋转右单旋转R型型左单旋转左单旋转L型型第57页，本讲稿共151页左右双旋转左右双旋转LR型型右左双旋转右左双旋转RL型型第58页，本讲稿共151页左单旋转左单旋转(RotateLeft,L型型)第59页，本讲稿共151页hhhACEBDhhh+1BACEDhhh+1CEABD+1+1+2+20 0+1+10 00 0 在子树在子树E中插入新结点，该子树中插入新结点，该子树 高度增高度增 1导致结点导致结点 A的平衡因子的平衡因子 变成变成 +2，产生不平衡，产生不平衡(L型型)以

25、结点以结点C为旋转轴，将结点为旋转轴，将结点A反时针旋转反时针旋转第60页，本讲稿共151页右单旋转右单旋转(RotateRight,R型型)第61页，本讲稿共151页 在子树在子树D中插入新结点中插入新结点,该子树该子树 高度增高度增 1导致结点导致结点 A的平衡因子的平衡因子 变成变成 -2，产生不平衡，产生不平衡(R型型)以结点以结点B为旋转轴，将结点为旋转轴，将结点A顺时针旋转顺时针旋转hhhACEBDhh+1BACEDhhh+1CEABDh0 00 00 0-1 1-1 1-2 2第62页，本讲稿共151页先左后右双旋转先左后右双旋转(RotationLeftRight,LR型型)第

26、63页，本讲稿共151页 在子树在子树F或或G中插入新结点，该子树中插入新结点，该子树高度增高度增 1 导致结点导致结点 A 的平衡因子变成的平衡因子变成-2，产生不平衡，产生不平衡(LR型型)n n首首先先以以结结点点E为为旋旋转转轴轴，将将结结点点B反反时时针针旋旋转转，以以E代代替替原原来来B的的位位置置，做做左左单单旋旋转转n n再再以以结结点点E为为旋旋转转轴轴，将将结结点点A顺顺时时针针旋旋转转，做右单旋转做右单旋转第64页，本讲稿共151页插入0 00 0-1 1-2 2+1+1-1 1hhACED0 0 0 0h-1h-1hhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转

27、FGFG第65页，本讲稿共151页0 00 0-2 20 0 0 00 0+1+1hhACED-2 2h-1hhhAh-1hBCEDB右单右单右单右单旋转旋转旋转旋转FGFG第66页，本讲稿共151页先右后左双旋转先右后左双旋转(RotationRightLeft,RL型型)第67页，本讲稿共151页 在子树在子树F或或G中插入新结点，该子树中插入新结点，该子树高度增高度增 1 导致结点导致结点 A 的平衡因子变成的平衡因子变成2，产生不平衡，产生不平衡(RL型型)n n首首先先以以结结点点D为为旋旋转转轴轴，将将结结点点C顺顺时时针针旋旋转转，以以D代代替替原原来来C的的位位置置,做做右右单

28、单旋旋转转n n再再以以结结点点D为为旋旋转转轴轴，将将结结点点A反反时时针针旋旋转，做左单旋转转，做左单旋转第68页，本讲稿共151页插入插入插入插入右右右右单单单单旋旋旋旋转转转转+1+10 00 00 0-1 1+1+10 0hhACEDh-1BFGh-1+2+20 00 00 0hhACEhBFGh-1D第69页，本讲稿共151页0 00 0+2+20 0 0 0-1 10 0hhACE+2 2h-1hhhAh-1hBCEDB左单左单左单左单旋转旋转旋转旋转FGFGD第70页，本讲稿共151页构造二叉平衡（查找）树的方法构造二叉平衡（查找）树的方法在插入过程中，采用平衡旋转技术在插入过

29、程中，采用平衡旋转技术依次插入的关键字为依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转第71页，本讲稿共151页426589642895向左旋转一次继续插入关键字继续插入关键字 9第72页，本讲稿共151页输入关键码序列为输入关键码序列为 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 71

30、690 00 00 037 71126916110 01 11 12 2 2 2第73页，本讲稿共151页右左双旋右左双旋左单左单18183-1 1160 00 00 0732611-1 19716140 00 02691 1110 03160 02 27390 0182611-1 11691 1711261 1第74页，本讲稿共151页15182 231816-2 2左右双旋左右双旋730 00 00 0117149-1 116150 01 1112626141 1-2 29从空树开始的建树过程第75页，本讲稿共151页B 树大型文件访问方法第76页，本讲稿共151页B树是一种 平衡 的 多

31、路 查找 树第77页，本讲稿共151页 在在 m 阶的阶的B树上，每个非终端结点树上，每个非终端结点可能含有：可能含有：n 个关键字个关键字 Ki（1 in）nm n 个指向记录的指针个指向记录的指针 Di（1in）n+1 个指向子树的指针个指向子树的指针 Ai（0in）多叉树的特性第78页，本讲稿共151页 非叶结点中的多个关键字均自小至大有序排非叶结点中的多个关键字均自小至大有序排列，即：列，即：K1 K2 Kn Ai-1 所指子树上所有关键字均小于所指子树上所有关键字均小于Ki Ai 所指子树上所有关键字均大于所指子树上所有关键字均大于Ki查找树的特性第79页，本讲稿共151页平衡树的特

32、性 树中所有叶子结点均不带信息，且在树树中所有叶子结点均不带信息，且在树中的同一层次上中的同一层次上 根结点或为叶子结点，或至少含有两棵根结点或为叶子结点，或至少含有两棵子树子树 其余所有非叶结点均至少含有其余所有非叶结点均至少含有 m/2 棵棵子树，子树，至多含有至多含有 m 棵子树棵子树第80页，本讲稿共151页 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行查找过程第81页，本讲稿共151页 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置 若查找不成功，则返回插入位置第82页，本讲稿共151页 在查找不成功之后，需进行插入 显然，关键

33、字插入的位置必定在最下层的非叶结点，有下列几种情况插 入第83页，本讲稿共151页插入后，该结点的关键字个数nm，不修改指针第84页，本讲稿共151页插入后，该结点的关键字个数插入后，该结点的关键字个数 n=m，则需进行则需进行“结点分裂结点分裂”，令，令 s=m/2，在原结点中保留在原结点中保留 （A0，K1，Ks-1，As-1）；）；建新结点建新结点 （As，Ks+1，Kn，An）；）；将（将（Ks，p）插入双亲结点）插入双亲结点第85页，本讲稿共151页若双亲为空，则建新的根结点第86页，本讲稿共151页下列为下列为 3 阶阶B树树50 20 40 80 插入关键字插入关键字=60 60

34、 80 ,90 60 80 90 90 50 80 60,30 40 20 30 50 8030 5080第87页，本讲稿共151页 和插入的考虑相反，首先必须找到待删关和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于键字的个数不能小于 m/2-1，否则，要从其左，否则，要从其左(或右或右)兄弟结点兄弟结点“借调借调”关键字，若其左和右关键字，若其左和右兄弟结点均无关键字可借兄弟结点均无关键字可借(结点中只有最少量的结点中只有最少量的关键字关键字)，则必须进行结点的，则必须进行结点的“合并合并”删 除第88页

35、，本讲稿共151页 在含 N 个关键字的 B树上进行一次查找，需访问的结点个数不超过 logm/2(N+1)/2)+1查找性能第89页，本讲稿共151页是B树的一种变型B+树第90页，本讲稿共151页 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点第91页，本讲稿共151页 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间第92页，本讲稿共151页查找过程 在 B+树上，既可以进行缩小范围的查找，

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

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

38、该结点中的子树棵数该结点中的子树棵数 n 小于结点子树棵数的下小于结点子树棵数的下限限 m/2，必须做结点的调整或合并工作。，必须做结点的调整或合并工作。第98页，本讲稿共151页删除18删除12第99页，本讲稿共151页 如如果果右右兄兄弟弟结结点点的的子子树树棵棵数数已已达达到到下下限限 m/2，没没有有多多余余的的关关键键码码可可以以移移入入被被删删关关键键码码所所在在的的结结点点，这这时时必必须须进进行行两两个个结结点点的的合合并并。将将右右兄兄弟弟结结点点中中的的所所有有关关键键码码-指指针针索索引引项项移移入入被被删删关键码所在结点，再将右兄弟结点删去。关键码所在结点，再将右兄弟结

39、点删去。第100页，本讲稿共151页删除删除3333进行进行结点合并结点合并第101页，本讲稿共151页 结结点点的的合合并并将将导导致致双双亲亲结结点点中中“分分界界关关键键码码”的的减减少少，有有可可能能减减到到非非叶叶结结点点中中子子树树棵棵数数的的下下限限 m/2 以以下下。这这样样将将引引起起非非叶叶结结点点的的调调整整或或合并。合并。如如果果根根结结点点的的最最后后两两个个子子女女结结点点合合并并，树树的的层层数数就会减少一层。就会减少一层。第102页，本讲稿共151页 The B*-Tree splits two pages for three,and combines thre

40、e pages into two.In this way,nodes are always 2/3 full.第103页，本讲稿共151页 Trie树是一棵度树是一棵度 m 2 的树，它的每一层分支不的树，它的每一层分支不是靠整个关键码的值来确定，而是由关键码的是靠整个关键码的值来确定，而是由关键码的一个分量来确定。一个分量来确定。如下图所示如下图所示Trie树，关键码由英文字母组成。它树，关键码由英文字母组成。它包括两类结点：元素结点和分支结点。元素结包括两类结点：元素结点和分支结点。元素结点包含整个点包含整个key数据；分支结点有数据；分支结点有27个指针，其个指针，其中有一个空白字符中有

41、一个空白字符b，用来终结关键码；其，用来终结关键码；其它用来标识它用来标识a,b,.,z等等26个英文字母。个英文字母。Trie树Trie树的定义树的定义当关键码是可变长时，当关键码是可变长时，Trie树是一种特别有用的索树是一种特别有用的索引结构。引结构。第104页，本讲稿共151页第105页，本讲稿共151页 在第在第0层，所有的关键码根据它们第层，所有的关键码根据它们第0位字符位字符,被被划分到互不相交的划分到互不相交的27个类中。个类中。因此，因此，rootbrch.linki 指向一棵子指向一棵子Trie树，该树，该子子Trie树上所包含的所有关键码都是以第树上所包含的所有关键码都是

42、以第 i 个个英文字母开头。英文字母开头。若某一关键码第若某一关键码第 j 位字母在英文字母表中顺序位字母在英文字母表中顺序为为 i (i=0,1,26),则它在则它在Trie树的第树的第 j 层层分支结点中从第分支结点中从第 i 个指针向下找第个指针向下找第 j+1 位字母位字母所在结点。当一棵子所在结点。当一棵子Trie树上只有一个关键码树上只有一个关键码时，就由一个元素结点来代替。在这个结点中时，就由一个元素结点来代替。在这个结点中包含有关键码，以及其它相关的信息，如对应包含有关键码，以及其它相关的信息，如对应数据对象的存放地址等。数据对象的存放地址等。第106页，本讲稿共151页 Tr

43、ie树的搜索树的搜索 为了在为了在Trie树上进行搜索，要求把关键码分树上进行搜索，要求把关键码分解成一些字符元素解成一些字符元素,并根据这些字符向下进并根据这些字符向下进行分支。行分支。第107页，本讲稿共151页在在TrieTrie树上插入树上插入bobwhite和和和和bluejay后的结果后的结果第108页，本讲稿共151页哈 希 查 找(Hash)第109页，本讲稿共151页 以上讨论的表示查找表的各种结以上讨论的表示查找表的各种结构的共同特点：记录在表中的位置构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定和它的关键字之间不存在一个确定的关系的关系第110页，本讲稿共1

44、51页 查找的过程为给定值依次和关查找的过程为给定值依次和关键字集合中各个关键字进行比较键字集合中各个关键字进行比较 查找的效率取决于和给定值进查找的效率取决于和给定值进行比较的关键字个数行比较的关键字个数第111页，本讲稿共151页 用这类方法表示的查找表，用这类方法表示的查找表，其平均查找长度都不为零其平均查找长度都不为零 不同的表示方法，其差别仅在不同的表示方法，其差别仅在于：于：关键字和给定值进行比较的顺关键字和给定值进行比较的顺序不同序不同第112页，本讲稿共151页 只有一个办法：预先知道所查关只有一个办法：预先知道所查关键字在表中的位置键字在表中的位置对于频繁使用的查找表，希望对

45、于频繁使用的查找表，希望ASL=0 即，要求：记录在表中位置和其即，要求：记录在表中位置和其关键字之间存在一种确定的关系关键字之间存在一种确定的关系第113页，本讲稿共151页 在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 H(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 H(key)为哈希函数第114页，本讲稿共151页 哈希函数是一个映象，即：将关键 字的集合映射到某个地址集合上，它 的设置很灵活，只要这个地址集合的 大小不超出允许范围即可第115页，本讲稿共151页 由于哈希函数是一个压缩由于哈希函数是一个压缩映象，因映象，因 此，在一般情况

46、，很此，在一般情况，很容易产生容易产生“冲冲 突突”现象，即：现象，即：key1 key2，而，而 H(key1)=H(key2)第116页，本讲稿共151页 很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生第117页，本讲稿共151页 因此，在构造这种特殊的因此，在构造这种特殊的“查查找表找表”时，除了需要选择一个时，除了需要选择一个“好好”(尽可能少产生冲突尽可能少产生冲突 )的哈希函数的哈希函数之外；还需要找到一种之外；还需要找到一种“处理冲突处理冲突”的方法的方法第118页，本讲稿共151页哈希表的定义 根据设定的哈希函数根据设定的哈希函数 H

47、(key)和所和所选处理冲突的方法，将一组关键字映象选处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集到一个有限的、地址连续的地址集(区区间间)上，并以关键字在地址集中的上，并以关键字在地址集中的“映映象象”作为相应记录在表中的存储位置，作为相应记录在表中的存储位置，如此构造所得的查找表称为如此构造所得的查找表称为“哈希表哈希表”第119页，本讲稿共151页构造哈希函数的方法对数字的关键字可有下列构造方法 若是非数字关键字，则需先对若是非数字关键字，则需先对其进行数字化处理其进行数字化处理 直接定址法直接定址法 平方取中法平方取中法 除留余数法除留余数法 折叠法折叠法 数字分析法

48、数字分析法第120页，本讲稿共151页数字分析法 第121页，本讲稿共151页 此方法适合于：能预先估计出全体关键字的每一位 上各种数字出现的频度 假设关键字集合中的每个关键字都假设关键字集合中的每个关键字都是由是由 s 位数字组成位数字组成(u1,u2,us)，分析关，分析关键字集中的全体，键字集中的全体，并从中提取分布均匀并从中提取分布均匀的若干位或它们的组合作为地址的若干位或它们的组合作为地址第122页，本讲稿共151页平方取中法第123页，本讲稿共151页 以关键字的平方值的中间几位作为以关键字的平方值的中间几位作为存储地址。求存储地址。求“关键字的平方值关键字的平方值”的目的目的是的

49、是“扩大差别扩大差别”，同时平方值的中间，同时平方值的中间各位又能受到整个关键字中各位的影响各位又能受到整个关键字中各位的影响 此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象第124页，本讲稿共151页折叠法第125页，本讲稿共151页 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加 此方法适合于:关键字的数字位数特别多第126页，本讲稿共151页直接定址法第127页，本讲稿共151页哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b此法适合于：地址集合的大小=关键字集合的大小第128页，本讲稿

50、共151页除留余数法第129页，本讲稿共151页 设定哈希函数为设定哈希函数为:H(key)=key MOD p 其中，其中，pm(表长表长)并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子第130页，本讲稿共151页 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小第131页，本讲稿共151页处理冲突的方法“处理冲突处理冲突”的实际含义是的实际含义是为产生冲突的地址寻找下一个哈希地址为产生冲突的地址寻找下一个哈希地址1.开放定址法2.链地址法第132