数据结构第九章PPT课件课件

《数据结构第九章PPT课件课件》由会员分享，可在线阅读，更多相关《数据结构第九章PPT课件课件（56页珍藏版）》请在装配图网上搜索。

1、数据结构第九章PPT课件1数据结构数据结构第九章第九章 查找查找数据结构第九章PPT课件2主要讨论的问题：静态查找主要讨论的问题：静态查找;动态查找动态查找;哈希查找哈希查找.几个基本概念几个基本概念.查找表查找表:由同一类型的数据元素构成的集合由同一类型的数据元素构成的集合.静态查找表静态查找表:若若只只在查找表中在查找表中搜索搜索某一特定的某一特定的数据元素是否存在数据元素是否存在,这类搜索过程称之为静态查这类搜索过程称之为静态查找找.动态查找表动态查找表:若在查找表中搜索时若在查找表中搜索时插入插入了不存了不存在的数据元素或在的数据元素或删除删除了已存在的数据元素了已存在的数据元素,这类

2、这类搜索过程称之为动态查找表搜索过程称之为动态查找表.数据结构第九章PPT课件3.关键字关键字:是数据元素中某个数据项的值是数据元素中某个数据项的值,它可以它可以标识一个数据元素标识一个数据元素.查找查找:根据给定的某个值根据给定的某个值,在查找表中确定一个在查找表中确定一个其关键字等于给定值的记录或数据元素其关键字等于给定值的记录或数据元素.查找成功查找成功:若表中存在这样的记录若表中存在这样的记录,称查找是成称查找是成功的功的.查找不成功查找不成功:若表中不存在关键字等于给定值若表中不存在关键字等于给定值的记录的记录,称查找不成功称查找不成功.数据结构第九章PPT课件49.1静态查找表静态

3、查找表.顺序表的查找的定义顺序表的查找的定义-又又称线性查找称线性查找,主要用于在线性结构中进行搜索主要用于在线性结构中进行搜索.顺序查找的思想顺序查找的思想-从表的一端开始从表的一端开始,用给定值用给定值k与表中各个结点的与表中各个结点的键值逐个比较键值逐个比较.1)查找成功查找成功-找出相等找出相等k值；值；2)查找失败查找失败-已到达表的另一端已到达表的另一端(可在此设置可在此设置一个一个监视哨监视哨，作为下标越界的条件，作为下标越界的条件),即表中所即表中所有结点的键值都不等于有结点的键值都不等于k.数据结构第九章PPT课件5.监视哨的作用监视哨的作用:作为越界作为越界(即已查完即已查

4、完)的检测条件的检测条件,省去在循环中每次均要判定是否越界省去在循环中每次均要判定是否越界,从而节省从而节省比较的时间比较的时间.顺序查找算法：顺序查找算法：int sxcz(JD r,int n,int k)int i=n;/*从表尾开始向前查找从表尾开始向前查找*/r0.key=k;/*设置监视哨设置监视哨*/while(ri.key!=k)i-;return(i);数据结构第九章PPT课件6.平均查找长度平均查找长度(在等概率的前提下在等概率的前提下)（n+1）/2.-平均查找长度平均查找长度ASL.如何衡量顺序查找的性能？如何衡量顺序查找的性能？.顺序查找的特点顺序查找的特点：1)算法

5、简单算法简单,对线性表的逻辑次序无要求对线性表的逻辑次序无要求(即不必即不必按关键字值不增或不减的次序排列按关键字值不增或不减的次序排列)；2)存储结构可采用顺序或链式存储结构均可存储结构可采用顺序或链式存储结构均可,但但其平均查找长度较大其平均查找长度较大(n+1)/2).数据结构第九章PPT课件7.思想思想:先确定待查找记录所在的范围先确定待查找记录所在的范围,然后逐步然后逐步缩小范围缩小范围,直到找到或确认找不到该记录为止直到找到或确认找不到该记录为止.二分查找二分查找.适用条件适用条件:必须在必须在具有顺序存储结构的有序表中具有顺序存储结构的有序表中进行进行.算法实现算法实现数据结构第

6、九章PPT课件8.思想思想:先确定待查找记录所在的范围先确定待查找记录所在的范围,然后逐步然后逐步缩小范围缩小范围,直到找到或确认找不到该记录为止直到找到或确认找不到该记录为止.二分查找二分查找.适用条件适用条件:必须在必须在具有顺序存储结构的有序表中具有顺序存储结构的有序表中进行进行.算法实现算法实现.设表长为设表长为n,low,high和和mid分别指向待查元素所在区间的上分别指向待查元素所在区间的上界界,下界和中点下界和中点,k为给定值为给定值.初始时初始时,令令low=1,high=n,mid=(low+high)/2（只舍不入）（只舍不入）.让让k与与mid指向的记录比较指向的记录比

7、较1)若若k=rmid.key,查找成功查找成功(k等于中间项的值等于中间项的值)2)若若krmid.key,则则low=mid+1(k大于中间值大于中间值,在表的后在表的后半部分查找半部分查找).重复上述操作重复上述操作,直至直至lowhigh时时,查找失败查找失败.数据结构第九章PPT课件9例例:在查找表在查找表(08,14,23,37,46,55,68,79,91)查找查找23和和79的过程的过程.二分查找的示例二分查找的示例.二分查找的算法描述二分查找的算法描述折半查找的折半查找的c语言算法程序：语言算法程序：int Search_Bin(SSTable ST,int n,int ke

8、y)int low,high,mid;low=1;high=n;while(low=high)mid=(low+high)/2;if(STmid.key=key)return(mid);/*查找成功查找成功*/else if(key STmid.key)high=mid-1;/*在前半区间继续查找在前半区间继续查找*/else low=mid+1;/*在后半区间继续查找在后半区间继续查找*/return(0);/*查找不成功查找不成功*/数据结构第九章PPT课件10.设有一有序表设有一有序表(-1,0,1,3,4,6,8,10,12),以二分查找以二分查找来构造出它的二叉判定树来构造出它的二叉

9、判定树.从有序表构造出二叉查找树从有序表构造出二叉查找树(二叉判定树二叉判定树)数据结构第九章PPT课件11.若设若设n=2h-1,则描述二分查找的二叉查找树是高则描述二分查找的二叉查找树是高度为度为h-1的满二叉树的满二叉树.2h=n+1,h=log2(n+1).第第1层结点有层结点有1个个,搜索第搜索第1层结点要比较层结点要比较1次次;第第2层层结点有结点有2个个,搜索第搜索第2层结点要比较层结点要比较2次次;,第第 i(0 i h)层结点有层结点有 2i 个个,搜索第搜索第 i 层结点要比层结点要比较较 i+1次次,.假定每个结点的搜索概率相等假定每个结点的搜索概率相等,即即pi=1/n

10、,则搜索成功的平均搜索长度为则搜索成功的平均搜索长度为:.二分查找的性能分析二分查找的性能分析hjjniiniiijncncpASL1111211数据结构第九章PPT课件12.可以用归纳法证明可以用归纳法证明12)1(22)1(2322111221hhhhhh1)1(log1)1(log1 )1(log)1(1)12)1(1 222nnnnnnnnhnASLhsucc.于是于是,可得可得.特点特点:比顺序查找方法效率高比顺序查找方法效率高.最坏的情况下最坏的情况下,需要需要比较比较 log2n+1次次,即时间复杂度为即时间复杂度为O(log2n).数据结构第九章PPT课件13.分块查找分块查找

11、(索引顺序查找索引顺序查找).是顺序查找的一种改进方法是顺序查找的一种改进方法,就是把被查找的表就是把被查找的表分成若干块分成若干块,每块中记录的存放顺序是无序的每块中记录的存放顺序是无序的,但但块与块之间必须按关键字有序块与块之间必须按关键字有序.即第一块中任一记即第一块中任一记录的关键字都小于第二块中任一记录的关键字录的关键字都小于第二块中任一记录的关键字,而而第二块中任一记录的关键字都小于第三块中任一第二块中任一记录的关键字都小于第三块中任一记录的关键字记录的关键字,依此类推依此类推.思想思想:该法要为被查找的表建立一个该法要为被查找的表建立一个索引表索引表,索引索引表中的一项对应于表中

12、的一块表中的一项对应于表中的一块,索引表中含有这一索引表中含有这一块中的块中的最大关键字最大关键字和和指向块内第一个记录位置的指向块内第一个记录位置的指针指针,索引表中各项索引表中各项关键字有序关键字有序.数据结构第九章PPT课件14索引表索引表 20 53 89 1 6 1118 12 8520 51 36 22 29 53 89 60 72 66 76块中的最大块中的最大关键字关键字块内第一块内第一个记录位个记录位置的指针置的指针分块查找分分块查找分两步两步进行进行:先查先查索引表索引表(索引表表长较短用顺序查找索引表表长较短用顺序查找,较较长可用折半查找长可用折半查找)确定纪录在哪一块确

13、定纪录在哪一块.然后在相应的然后在相应的块中查找块中查找.例例,查查找找12,12,由索引表的第一项知由索引表的第一项知,纪录要么在第一块中纪录要么在第一块中,要么不存在要么不存在,由此由此取到第一块中第一个纪录位置取到第一块中第一个纪录位置.接着在第一块中进行顺序查找接着在第一块中进行顺序查找.分块分块查找效率高于顺序查找查找效率高于顺序查找,但低于折半查找但低于折半查找.数据结构第九章PPT课件159.2动态查找表动态查找表.回忆回忆:动态查找表的特点动态查找表的特点.二叉排序树二叉排序树(二叉搜索树二叉搜索树)二叉排序树二叉排序树或者是或者是一棵空树一棵空树,或者是具有下列性质的或者是具

14、有下列性质的二叉树二叉树:每个结点都有一个作为搜索依据的关键码每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同所有结点的关键码互不相同.左子树左子树(如果存在如果存在)上所有结点的关键码都上所有结点的关键码都小于小于根结根结点的关键码点的关键码.右子树右子树(如果存在如果存在)上所有结点的关键码都上所有结点的关键码都大于大于根结根结点的关键码点的关键码.左子树和右子树也是二叉排序树左子树和右子树也是二叉排序树.的定义的定义数据结构第九章PPT课件16.几个二叉排序树的例子几个二叉排序树的例子.由此由此,可得到二叉排序树的作用可得到二叉排序树的作用:查找查找.二叉排序树上

15、的二叉排序树上的查找查找-在二叉搜索树上进行搜索在二叉搜索树上进行搜索,是一个从根结点开是一个从根结点开始始,沿某一个分支逐层向下进行比较判等的过程沿某一个分支逐层向下进行比较判等的过程.二叉排序树上的二叉排序树上的查找查找可以是一个可以是一个递归递归过程过程,也也可以是一个可以是一个迭代迭代过程过程.数据结构第九章PPT课件17.二叉排序树是的搜索示例二叉排序树是的搜索示例.88插入到哪个地方插入到哪个地方?.每次结点的插入每次结点的插入,都要从根结点出发搜索插入都要从根结点出发搜索插入位置位置,然后把新结点作为然后把新结点作为叶结点插入叶结点插入.数据结构第九章PPT课件18.二叉排序树上

16、的二叉排序树上的插入插入-为了向二叉搜索树中插入一个新元素为了向二叉搜索树中插入一个新元素,必须先必须先检查这个元素是否在树中已经存在检查这个元素是否在树中已经存在.在插入之前在插入之前,先使用先使用搜索算法搜索算法在树中检查要插在树中检查要插入元素有还是没有入元素有还是没有.搜索成功搜索成功:树中已有这个元素树中已有这个元素,不再插入不再插入.搜索不成功搜索不成功:树中原来没有关键码等于给定树中原来没有关键码等于给定值的结点值的结点,把新元素把新元素加到搜索操作停止加到搜索操作停止的地的地方方.例例:输入数据序列输入数据序列53,78,65,17,87,09,81,45,23,写出建立二叉排

17、序树的过程写出建立二叉排序树的过程.数据结构第九章PPT课件19.为了引入二叉排序树上的删除为了引入二叉排序树上的删除,先简单讨论下先简单讨论下面这个问题面这个问题.同样同样 3 个数据个数据 1,2,3,输入顺序不同输入顺序不同,建立起建立起来的二叉搜索树的形态也不同来的二叉搜索树的形态也不同.这直接影响到二这直接影响到二叉搜索树的搜索性能叉搜索树的搜索性能.如果输入序列选得不好如果输入序列选得不好,会建立起一棵单支树会建立起一棵单支树,使得二叉搜索树的高度达到最大使得二叉搜索树的高度达到最大,这样必然会降这样必然会降低搜索性能低搜索性能.123111132223323直观上直观上的结论的结

18、论,二叉二叉排序树的高度不能排序树的高度不能太高太高.数据结构第九章PPT课件20.二叉排序树上的二叉排序树上的删除删除-在二叉搜索树中删除一个结点时在二叉搜索树中删除一个结点时,必须将因删必须将因删除结点而断开的二叉链表重新链接起来除结点而断开的二叉链表重新链接起来,同时确同时确保二叉搜索树的性质不会失去保二叉搜索树的性质不会失去.为保证在执行删除后为保证在执行删除后,树的搜索性能不至于降低树的搜索性能不至于降低,还需要防止重新链接后树的还需要防止重新链接后树的高度增加高度增加.1)删除叶结点删除叶结点,只需将其双亲结点指向它的指针清只需将其双亲结点指向它的指针清零零,再释放它即可再释放它即

19、可.2)被删结点缺右子树被删结点缺右子树,可以拿它的左子女结点顶替可以拿它的左子女结点顶替它的位置它的位置,再释放它再释放它.3)被删结点缺左子树被删结点缺左子树,可以拿它的右子女结点顶替可以拿它的右子女结点顶替它的位置，再释放它它的位置，再释放它.数据结构第九章PPT课件214)被删结点左被删结点左,右子树都存在右子树都存在,可以在它的右子树可以在它的右子树中寻找中序下的第一个结点中寻找中序下的第一个结点(关键码最小关键码最小),用它的用它的值填补到被删结点中值填补到被删结点中,再来处理这个结点的删除再来处理这个结点的删除问题问题.数据结构第九章PPT课件22.二叉排序树上的二叉排序树上的查

20、找性能分析查找性能分析.二叉排序树上的查找与折半查找类似二叉排序树上的查找与折半查找类似.但但,折半查找长度为折半查找长度为n的表的判定树惟一的表的判定树惟一.显然显然,n个结点的二叉排序树的平均查找长度与树个结点的二叉排序树的平均查找长度与树的二叉树的形态有关的二叉树的形态有关.想想想想,最好情况最好情况与与最坏情况最坏情况各是什么样各是什么样?.结论结论:在随机情况下在随机情况下,二叉排序树的平均查找长度二叉排序树的平均查找长度是对数级是对数级.但这种情况出现的概率小于但这种情况出现的概率小于50%.结论结论:在构建二叉排序树的过程中要进行在构建二叉排序树的过程中要进行”平衡平衡化化”处理

21、处理.数据结构第九章PPT课件23.平衡二叉树平衡二叉树(AVL树树).AVL树的定义树的定义.一棵一棵AVL树或者是空树树或者是空树,或者是具有下列性质的或者是具有下列性质的二叉搜索树二叉搜索树:它的左子树和右子树都是它的左子树和右子树都是AVL树树,且且左子树和右子树的高度之差的绝对值不超过左子树和右子树的高度之差的绝对值不超过1.(a)(b)数据结构第九章PPT课件24.结点的平衡因子结点的平衡因子.每个结点附加一个数字每个结点附加一个数字,给出该结点右给出该结点右(左左)子树子树的高度减去左的高度减去左(右右)子树的高度所得的高度差子树的高度所得的高度差.这个这个数字即为结点的平衡因子

22、数字即为结点的平衡因子balance.如果一个结点的平衡因子的绝对值大于如果一个结点的平衡因子的绝对值大于1,则这棵则这棵二叉搜索树就失去了平衡二叉搜索树就失去了平衡,不再是不再是AVL树树.任何一个结点的平任何一个结点的平衡因子有几个取值衡因子有几个取值?.一棵一棵AVL树的高度保持在什么级别树的高度保持在什么级别?.高度可保持在高度可保持在O(log2n).数据结构第九章PPT课件25.平衡化处理平衡化处理.平衡化旋转有两类：平衡化旋转有两类：单旋转单旋转(左旋和右旋左旋和右旋)双旋转双旋转(左平衡和右平衡左平衡和右平衡).每插入一个新结点时每插入一个新结点时,AVL树中相关结点的平衡树中

23、相关结点的平衡状态会发生改变状态会发生改变.因此因此,在插入一个新结点后在插入一个新结点后,需要需要从插入位置沿通向根的路径回溯从插入位置沿通向根的路径回溯,检查各结点的检查各结点的平衡因子平衡因子(左左,右子树的高度差右子树的高度差).如果在某一结点发如果在某一结点发现高度不平衡现高度不平衡,停止回溯停止回溯.数据结构第九章PPT课件26.从发生不平衡的结点起从发生不平衡的结点起,沿刚才回溯的路径取直接沿刚才回溯的路径取直接下两层的结点下两层的结点.如果这三个结点处于一条直线上，则采用单旋转如果这三个结点处于一条直线上，则采用单旋转进行平衡化进行平衡化.单旋转可按其方向分为左单旋转和右单旋转

24、可按其方向分为左单旋转和右单旋转单旋转,其中一个是另一个的镜像其中一个是另一个的镜像,其方向与不平衡其方向与不平衡的形状相关的形状相关.如果这三个结点处于一条折线上，则采用双旋转如果这三个结点处于一条折线上，则采用双旋转进行平衡化进行平衡化.双旋转分为先左后右和先右后左两类双旋转分为先左后右和先右后左两类.数据结构第九章PPT课件27.AVL树的插入树的插入例例:输入关键码序列为输入关键码序列为 16,3,7,11,9,26,18,14,15,写出插入和调整过程写出插入和调整过程.161631637731673117316161193716937112691611数据结构第九章PPT课件281

25、8183163167391826117326161199716147112626911数据结构第九章PPT课件29151831816731171491615112626149例例:以以 30,35,39,15,10,28,16,29,17为例建为例建AVL树树.数据结构第九章PPT课件30.动态的动态的m路搜索树路搜索树.二叉搜索树适合于组织在内存中的较小的索引二叉搜索树适合于组织在内存中的较小的索引(或目录或目录),对于存放在对于存放在外存外存中的较大的文件系统中的较大的文件系统,用二叉搜索树来组织索引不太合适用二叉搜索树来组织索引不太合适.在文件检索系统中大量使用的是用在文件检索系统中大量

26、使用的是用B-(B)树树或或B+树树做文件索引做文件索引.当数据对象数目特别大当数据对象数目特别大,索引表本身也很大索引表本身也很大,在内在内存中放不下存中放不下,需要分批多次读取外存才能把索引需要分批多次读取外存才能把索引表搜索一遍表搜索一遍.数据结构第九章PPT课件31.在此情况下在此情况下,可以建立索引的索引可以建立索引的索引,称为二级索引称为二级索引.二级索引可以常驻内存二级索引可以常驻内存,二级索引中一个索引项二级索引中一个索引项对应一个索引块对应一个索引块,登记该索引块的最大关键码及登记该索引块的最大关键码及该索引块的存储地址该索引块的存储地址.如果二级索引在内存中也放不下如果二级

27、索引在内存中也放不下,需要分为许多需要分为许多块多次从外存读入块多次从外存读入.可以建立二级索引的索引，可以建立二级索引的索引，叫做三级索引叫做三级索引.这时这时,访问外存次数等于读入索引访问外存次数等于读入索引次数再加上次数再加上1次读取对象次读取对象.必要的话必要的话,还可以有还可以有4级索引级索引,5极索引极索引,.多级索引结构形成多级索引结构形成一种一种 m 叉树叉树.数据结构第九章PPT课件32.树中每一个树中每一个分支结点分支结点表示一个索引块表示一个索引块,它最多存它最多存放放 m 个索引项个索引项,每个索引项分别给出各子树结点每个索引项分别给出各子树结点(低一级索引块低一级索引

28、块)的最大关键码和结点地址的最大关键码和结点地址.树的树的叶结点叶结点中各索引项给出在数据表中存放的中各索引项给出在数据表中存放的对象的关键码和存放地址对象的关键码和存放地址.这种这种m叉树用来作为叉树用来作为多级索引多级索引,就是就是m路搜索树路搜索树.m路搜索树路搜索树可能是可能是静态索引结构静态索引结构,即结构在初始即结构在初始创建创建,数据装入时就已经定型数据装入时就已经定型,在整个运行期间在整个运行期间,树树的结构不发生变化的结构不发生变化.m路搜索树路搜索树还可能是还可能是动态索引结构动态索引结构,即在整个系即在整个系统运行期间统运行期间,树的结构随数据的增删及时调整树的结构随数据

29、的增删及时调整,以以保持保持最佳的搜索效率最佳的搜索效率.数据结构第九章PPT课件33多级索引结构形成多级索引结构形成 m 路搜索树路搜索树数据结构第九章PPT课件34.动态的动态的 m 路搜索树路搜索树.一般定义为一般定义为:.一棵一棵 m 路搜索树路搜索树,它或者是一棵空树它或者是一棵空树,或者是满或者是满足如下性质的树：足如下性质的树：根最多有根最多有 m 棵子树棵子树,并具有如下的结构：并具有如下的结构：n,P0,(K1,P1),(K2,P2),(Kn,Pn)其中，其中，Pi 是指向子树的指针是指向子树的指针,0 i n m;Ki 是关键码是关键码,1 i n m.Ki Ki+1,1

30、i n.在子树在子树 Pi 中所有的关键码都中所有的关键码都小于小于 Ki+1，且，且大于大于 Ki,0 i n.在子树在子树 Pn 中所有的关键码都中所有的关键码都大于大于Kn.在子树在子树 P0 中的所有关键码都中的所有关键码都小于小于 K1.子树子树 Pi 也是也是 m 路搜索树路搜索树,0 i n.数据结构第九章PPT课件35.一棵一棵3路搜索树的示例路搜索树的示例.AVL树是树是m=?路搜索树路搜索树?数据结构第九章PPT课件36.B-树树.一棵一棵 m 阶阶B_树是一棵树是一棵 m 路搜索树路搜索树,它或者是空它或者是空树树,或者是满足下列性质的树或者是满足下列性质的树:.根结点根

31、结点至少有至少有 2 个子女个子女.除根结点以外的所有结点除根结点以外的所有结点(不包括失败结点不包括失败结点)至少有至少有 m/2 个子女个子女.所有的失败结点都位于同一层所有的失败结点都位于同一层.事实上事实上,在在B-树的树的每个结点每个结点中还包含有一组指针中还包含有一组指针Dm,指向实际对象的存放地址指向实际对象的存放地址.Ki与与Di(1 i n m)形成一个索引项形成一个索引项(Ki,Di).通过通过Ki可可找到某个对象的存储地址找到某个对象的存储地址Di.数据结构第九章PPT课件37.非非B-树与树与B-树的示例图树的示例图非非B-树树B-树树.B-树上的树上的搜索搜索数据结构

32、第九章PPT课件38.B-树的搜索过程是一个在树的搜索过程是一个在结点内搜索结点内搜索和和循某一循某一条路径向下一层搜索条路径向下一层搜索交替进行的过程交替进行的过程.因此因此,B-树树的搜索时间与的搜索时间与B-树的阶数树的阶数m和和B-树的高度树的高度h直接直接有关有关,必须加以权衡必须加以权衡.在在B-树上进行搜索树上进行搜索,搜索成功搜索成功所需的时间取决于所需的时间取决于关键码所在的关键码所在的层次层次,搜索不成功搜索不成功所需的时间取决所需的时间取决于于树的高度树的高度.在在B-树上搜索的示例树上搜索的示例数据结构第九章PPT课件39.B-树上的树上的插入插入.B-树是从空树起树是

33、从空树起,逐个插入关键码而生成的逐个插入关键码而生成的.在在B-树树,每个非失败结点的关键码个数都在每个非失败结点的关键码个数都在 m/2 -1,m-1之间之间.插入在插入在某个叶结点某个叶结点开始开始.如果在关键码插入后结如果在关键码插入后结点中的关键码个数超出了上界点中的关键码个数超出了上界 m-1,则结点需要则结点需要“分裂分裂”,否则可以直接插入否则可以直接插入.实现实现“分裂分裂”的原则的原则数据结构第九章PPT课件40.设结点设结点 p 中已经有中已经有 m-1个关键码个关键码,当再插入一个当再插入一个关键码后结点中的状态为关键码后结点中的状态为:.数据结构第九章PPT课件41结点

34、结点“分裂分裂”的示例的示例数据结构第九章PPT课件42.B-树上的树上的插入示例插入示例:从空树开始逐个加入关键码从空树开始逐个加入关键码53,75,139,49,145,36,101建立建立3阶阶B-树树.数据结构第九章PPT课件43.若设若设B-树的高度为树的高度为h.那么在那么在自顶向下自顶向下搜索到搜索到叶叶结点结点的过程中需要进行的过程中需要进行h次读盘次读盘.在插入新关键码时在插入新关键码时,需要自底向上分裂结点需要自底向上分裂结点,最坏最坏情况下从被插关键码所在叶结点到根的路径上情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂的所有结点都要分裂.数据结构第九章PPT课

35、件44.B-树上的树上的删除删除.在在B-树上删除一个关键码时树上删除一个关键码时,首先需要找到这个首先需要找到这个关键码所在的结点关键码所在的结点,从中删去这个关键码从中删去这个关键码.若该结点不是叶结点若该结点不是叶结点,且被删关键码为且被删关键码为 Ki,1 i n,则在删去该关键码之后则在删去该关键码之后,应以该结点应以该结点 Pi 所指示所指示子树中的最小关键码子树中的最小关键码x来代替被删关键码来代替被删关键码 Ki 所在所在的位置的位置,然后在然后在x所在的叶结点中删除所在的叶结点中删除 x.在叶结点上删除有在叶结点上删除有4种情况种情况:1)被删关键码所在叶结点同时又是根结点且

36、删除被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数前该结点中关键码个数 n 2,则直接删去该关键则直接删去该关键码并将修改后的结点写回磁盘码并将修改后的结点写回磁盘.数据结构第九章PPT课件452)被删关键码所在叶结点不是根结点且删除前该被删关键码所在叶结点不是根结点且删除前该结点中关键码个数结点中关键码个数 n m/2,则直接删去该关键则直接删去该关键码并将修改后的结点写回磁盘码并将修改后的结点写回磁盘,删除结束删除结束.数据结构第九章PPT课件463)被删关键码所在叶结点删除前关键码个数被删关键码所在叶结点删除前关键码个数 n=m/2 -1,若这时与该结点相邻的右兄弟若这时与

37、该结点相邻的右兄弟(或左兄弟或左兄弟)结点的关键结点的关键码个数码个数 n m/2，则可按以下步骤调整该结点，则可按以下步骤调整该结点,右兄弟右兄弟(或左兄弟或左兄弟)结点以及其双亲结点结点以及其双亲结点,以达到新的平衡。以达到新的平衡。.将双亲结点中刚刚大于将双亲结点中刚刚大于(或小于或小于)该被删关键码的关该被删关键码的关键码键码 Ki (1 i n)下移；下移；.将右兄弟将右兄弟(或左兄弟或左兄弟)结点中的最小结点中的最小(或最大或最大)关键码关键码上移到双亲结点的上移到双亲结点的 Ki 位置；位置；.将右兄弟将右兄弟(或左兄弟或左兄弟)结点中的最左结点中的最左(或最右或最右)子树指子树

38、指针平移到被删关键码所在结点中最后针平移到被删关键码所在结点中最后(或最前或最前)子树子树指针位置；指针位置；.在右兄弟在右兄弟(或左兄弟或左兄弟)结点中结点中,将被移走的关键码和指将被移走的关键码和指针位置用剩余的关键码和指针填补针位置用剩余的关键码和指针填补,调整调整.再将结点中再将结点中的关键码个数减的关键码个数减1.数据结构第九章PPT课件47数据结构第九章PPT课件48数据结构第九章PPT课件494)被删关键码所在叶结点删除前关键码个数被删关键码所在叶结点删除前关键码个数n=m/2 -1,若这时与该结点相邻的右兄弟若这时与该结点相邻的右兄弟(或左兄弟或左兄弟)结点的关键码结点的关键码

39、个数个数 n=m/2 -1,则必须按以下步骤合并这两个结点则必须按以下步骤合并这两个结点.将将双亲结点双亲结点 p 中相应关键码下移到选定保留的结点中中相应关键码下移到选定保留的结点中.若要合并若要合并 p 中的子树指针中的子树指针 Pi 与与 Pi+1 所指的结点所指的结点,且保留且保留 Pi 所指结点所指结点,则把则把 p 中的关键码中的关键码 Ki+1下移到下移到 Pi 所指的结所指的结点中点中.把把 p 中子树指针中子树指针 Pi+1 所指结点中的全部指针和关键码所指结点中的全部指针和关键码都照搬到都照搬到 Pi 所指结点的后面所指结点的后面.删去删去 Pi+1 所指的结点所指的结点.

40、在结点在结点 p中用后面剩余的关键码和指针填补关键码中用后面剩余的关键码和指针填补关键码 Ki+1 和指针和指针 Pi+1.修改结点修改结点 p和选定保留结点的关键码个数和选定保留结点的关键码个数.在合并结点的过程中在合并结点的过程中,双亲结点中的关键码个数减双亲结点中的关键码个数减少了少了.数据结构第九章PPT课件50.若双亲结点是根结点且结点关键码个数减到若双亲结点是根结点且结点关键码个数减到 0，则该双亲结点应从树上删去则该双亲结点应从树上删去,合并后保留的结点成合并后保留的结点成为新的根结点为新的根结点;否则将双亲结点与合并后保留的结否则将双亲结点与合并后保留的结点都写回磁盘点都写回磁盘,删除处理结束删除处理结束.若双亲结点不是根结点若双亲结点不是根结点,且关键码个数减到且关键码个数减到 m/2 -2,又要与它自己的兄弟结点合并又要与它自己的兄弟结点合并,重复上面的合并步重复上面的合并步骤骤.最坏情况下这种结点合并处理要自下向上直到最坏情况下这种结点合并处理要自下向上直到根结点根结点.数据结构第九章PPT课件51数据结构第九章PPT课件52数据结构第九章PPT课件53数据结构第九章PPT课件54数据结构第九章PPT课件55数据结构第九章PPT课件56