《数据结构第九章幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第九章幻灯片.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第九章1第1页，共56页，编辑于2022年，星期六主要讨论的问题：静态查找主要讨论的问题：静态查找;动态查找动态查找;哈希查找哈希查找.几个基本概念几个基本概念.查找表查找表:由同一类型的数据元素构成的集合由同一类型的数据元素构成的集合.静态查找表静态查找表:若若只只在查找表中在查找表中搜索搜索某一特定的数某一特定的数据元素是否存在据元素是否存在,这类搜索过程称之为静态查找这类搜索过程称之为静态查找.动态查找表动态查找表:若在查找表中搜索时若在查找表中搜索时插入插入了不存在了不存在的数据元素或的数据元素或删除删除了已存在的数据元素了已存在的数据元素,这类搜索过这类搜索过程称之为动态查找
2、表程称之为动态查找表.第2页，共56页，编辑于2022年，星期六.关键字关键字:是数据元素中某个数据项的值是数据元素中某个数据项的值,它可以标识它可以标识一个数据元素一个数据元素.查找查找:根据给定的某个值根据给定的某个值,在查找表中确定一个其在查找表中确定一个其关键字等于给定值的记录或数据元素关键字等于给定值的记录或数据元素.查找成功查找成功:若表中存在这样的记录若表中存在这样的记录,称查找是成称查找是成功的功的.查找不成功查找不成功:若表中不存在关键字等于给定值若表中不存在关键字等于给定值的记录的记录,称查找不成功称查找不成功.3第3页，共56页，编辑于2022年，星期六9.1静态查找表静
3、态查找表.顺序表的查找的定义顺序表的查找的定义-又又称线性查找称线性查找,主要用于在线性结构中进行搜索主要用于在线性结构中进行搜索.顺序查找的思想顺序查找的思想-从表的一端开始从表的一端开始,用给定值用给定值k与表中各个结点的键值与表中各个结点的键值逐个比较逐个比较.1)查找成功查找成功-找出相等找出相等k值；值；2)查找失败查找失败-已到达表的另一端已到达表的另一端(可在此设置一个可在此设置一个监视哨监视哨，作为下标越界的条件，作为下标越界的条件),即表中所有结点即表中所有结点的键值都不等于的键值都不等于k.4第4页，共56页，编辑于2022年，星期六.监视哨的作用监视哨的作用:作为越界作为
4、越界(即已查完即已查完)的检测条件的检测条件,省去在循环中每次均要判定是否越界省去在循环中每次均要判定是否越界,从而节省从而节省比较的时间比较的时间.顺序查找算法：顺序查找算法：int sxcz(JD r,int n,int k)int i=n;/*从表尾开始向前查找从表尾开始向前查找*/r0.key=k;/*设置监视哨设置监视哨*/while(ri.key!=k)i-;return(i);5第5页，共56页，编辑于2022年，星期六.平均查找长度平均查找长度(在等概率的前提下在等概率的前提下)（n+1）/2.-平均查找长度平均查找长度ASL.如何衡量顺序查找的性能？如何衡量顺序查找的性能？.
5、顺序查找的特点顺序查找的特点：1)算法简单算法简单,对线性表的逻辑次序无要求对线性表的逻辑次序无要求(即不必按即不必按关键字值不增或不减的次序排列关键字值不增或不减的次序排列)；2)存储结构可采用顺序或链式存储结构均可存储结构可采用顺序或链式存储结构均可,但其但其平均查找长度较大平均查找长度较大(n+1)/2).6第6页，共56页，编辑于2022年，星期六.思想思想:先确定待查找记录所在的范围先确定待查找记录所在的范围,然后逐步缩小然后逐步缩小范围范围,直到找到或确认找不到该记录为止直到找到或确认找不到该记录为止.二分查找二分查找.适用条件适用条件:必须在必须在具有顺序存储结构的有序表中进行具
6、有顺序存储结构的有序表中进行.算法实现算法实现7第7页，共56页，编辑于2022年，星期六.思想思想:先确定待查找记录所在的范围先确定待查找记录所在的范围,然后逐步缩小然后逐步缩小范围范围,直到找到或确认找不到该记录为止直到找到或确认找不到该记录为止.二分查找二分查找.适用条件适用条件:必须在必须在具有顺序存储结构的有序表中进行具有顺序存储结构的有序表中进行.算法实现算法实现.设表长为设表长为n,low,high和和mid分别指向待查元素所在区间的上界分别指向待查元素所在区间的上界,下界和中点下界和中点,k为给定值为给定值.初始时初始时,令令low=1,high=n,mid=(low+high
7、)/2（只舍不入）（只舍不入）.让让k与与mid指向的记录比较指向的记录比较1)若若k=rmid.key,查找成功查找成功(k等于中间项的值等于中间项的值)2)若若krmid.key,则则low=mid+1(k大于中间值大于中间值,在表的后半部分查在表的后半部分查找找).重复上述操作重复上述操作,直至直至lowhigh时时,查找失败查找失败.8第8页，共56页，编辑于2022年，星期六例例:在查找表在查找表(08,14,23,37,46,55,68,79,91)查找查找23和和79的过程的过程.二分查找的示例二分查找的示例.二分查找的算法描述二分查找的算法描述折半查找的折半查找的c语言算法程序
8、：语言算法程序：int Search_Bin(SSTable ST,int n,int key)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);/*查找不成功查找不成功*/9第9页，共56页，编辑于2022年，星期六.设有一有序表设有一有
9、序表(-1,0,1,3,4,6,8,10,12),以二分查找以二分查找来构造出它的二叉判定树来构造出它的二叉判定树.从有序表构造出二叉查找树从有序表构造出二叉查找树(二叉判定树二叉判定树)10第10页，共56页，编辑于2022年，星期六.若设若设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 个个,
10、搜索第搜索第 i 层结点要比较层结点要比较 i+1次次,.假定每个结点的搜索概率相等假定每个结点的搜索概率相等,即即pi=1/n,则搜则搜索成功的平均搜索长度为索成功的平均搜索长度为:.二分查找的性能分析二分查找的性能分析11第11页，共56页，编辑于2022年，星期六.可以用归纳法证明可以用归纳法证明.于是于是,可得可得.特点特点:比顺序查找方法效率高比顺序查找方法效率高.最坏的情况下最坏的情况下,需要比较需要比较 log2n+1次次,即时间复杂度为即时间复杂度为O(log2n).12第12页，共56页，编辑于2022年，星期六.分块查找分块查找(索引顺序查找索引顺序查找).是顺序查找的一种
11、改进方法是顺序查找的一种改进方法,就是把被查找的表分成若就是把被查找的表分成若干块干块,每块中记录的存放顺序是无序的每块中记录的存放顺序是无序的,但块与块之间必但块与块之间必须按关键字有序须按关键字有序.即第一块中任一记录的关键字都小于即第一块中任一记录的关键字都小于第二块中任一记录的关键字第二块中任一记录的关键字,而第二块中任一记录的关而第二块中任一记录的关键字都小于第三块中任一记录的关键字键字都小于第三块中任一记录的关键字,依此类推依此类推.思想思想:该法要为被查找的表建立一个该法要为被查找的表建立一个索引表索引表,索引表索引表中的一项对应于表中的一块中的一项对应于表中的一块,索引表中含有
12、这一块中的索引表中含有这一块中的最最大关键字大关键字和和指向块内第一个记录位置的指针指向块内第一个记录位置的指针,索引表索引表中各项中各项关键字有序关键字有序.13第13页，共56页，编辑于2022年，星期六索引表索引表 20 53 89 1 6 1118 12 8520 51 36 22 29 53 89 60 72 66 76块中的最大关键字块内第一个记录位置的指针分分块块查查找找分分两两步步进进行行:先先查查索索引引表表(索索引引表表表表长长较较短短用用顺顺序序查查找找,较较长长可可用用折折半半查查找找)确确定定纪纪录录在在哪哪一一块块.然然后后在在相相应应的的块块中中查查找找.例例,查
13、查找找12,12,由由索索引引表表的的第第一一项项知知,纪纪录录要要么么在在第第一一块块中中,要要么么不不存存在在,由由此此取取到到第第一一块块中中第第一一个个纪纪录录位位置置.接接着着在在第第一一块块中中进进行行顺顺序序查查找找.分分块块查查找找效效率率高高于于顺顺序序查查找找,但但低低于折半查找于折半查找.14第14页，共56页，编辑于2022年，星期六9.2动态查找表动态查找表.回忆回忆:动态查找表的特点动态查找表的特点.二叉排序树二叉排序树(二叉搜索树二叉搜索树)二叉排序树二叉排序树或者是或者是一棵空树一棵空树,或者是具有下列性质的二或者是具有下列性质的二叉树叉树:每个结点都有一个作为
14、搜索依据的关键码每个结点都有一个作为搜索依据的关键码(key)，所，所有结点的关键码互不相同有结点的关键码互不相同.左子树左子树(如果存在如果存在)上所有结点的关键码都上所有结点的关键码都小于小于根结点的根结点的关键码关键码.右子树右子树(如果存在如果存在)上所有结点的关键码都上所有结点的关键码都大于大于根结点的根结点的关键码关键码.左子树和右子树也是二叉排序树左子树和右子树也是二叉排序树.的定义的定义15第15页，共56页，编辑于2022年，星期六.几个二叉排序树的例子几个二叉排序树的例子.由此由此,可得到二叉排序树的作用可得到二叉排序树的作用:查找查找.二叉排序树上的二叉排序树上的查找查找
15、-在二叉搜索树上进行搜索在二叉搜索树上进行搜索,是一个从根结点开始是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程沿某一个分支逐层向下进行比较判等的过程.二叉排序树上的二叉排序树上的查找查找可以是一个可以是一个递归递归过程过程,也可也可以是一个以是一个迭代迭代过程过程.16第16页，共56页，编辑于2022年，星期六.二叉排序树是的搜索示例二叉排序树是的搜索示例.88插入到哪个地方插入到哪个地方?.每次结点的插入每次结点的插入,都要从根结点出发搜索插入位都要从根结点出发搜索插入位置置,然后把新结点作为然后把新结点作为叶结点插入叶结点插入.17第17页，共56页，编辑于2022年，星期
16、六.二叉排序树上的二叉排序树上的插入插入-为了向二叉搜索树中插入一个新元素为了向二叉搜索树中插入一个新元素,必须先必须先检查这个元素是否在树中已经存在检查这个元素是否在树中已经存在.在插入之前在插入之前,先使用先使用搜索算法搜索算法在树中检查要插入元在树中检查要插入元素有还是没有素有还是没有.搜索成功搜索成功:树中已有这个元素树中已有这个元素,不再插入不再插入.搜索不成功搜索不成功:树中原来没有关键码等于给定值树中原来没有关键码等于给定值的结点的结点,把新元素把新元素加到搜索操作停止加到搜索操作停止的地方的地方.例例:输入数据序列输入数据序列53,78,65,17,87,09,81,45,23
17、,写出建立二叉排序树的过程写出建立二叉排序树的过程.18第18页，共56页，编辑于2022年，星期六.为了引入二叉排序树上的删除为了引入二叉排序树上的删除,先简单讨论下面这先简单讨论下面这个问题个问题.同样同样 3 个数据个数据 1,2,3,输入顺序不同输入顺序不同,建立起来的建立起来的二叉搜索树的形态也不同二叉搜索树的形态也不同.这直接影响到二叉搜索树这直接影响到二叉搜索树的搜索性能的搜索性能.如果输入序列选得不好如果输入序列选得不好,会建立起一棵单支树会建立起一棵单支树,使得二叉搜索树的高度达到最大使得二叉搜索树的高度达到最大,这样必然会降低这样必然会降低搜索性能搜索性能.12311113
18、2223323直观上直观上的结论的结论,二叉二叉排序树的高度不能排序树的高度不能太高太高.19第19页，共56页，编辑于2022年，星期六.二叉排序树上的二叉排序树上的删除删除-在二叉搜索树中删除一个结点时在二叉搜索树中删除一个结点时,必须将因删除结必须将因删除结点而断开的二叉链表重新链接起来点而断开的二叉链表重新链接起来,同时确保二叉搜同时确保二叉搜索树的性质不会失去索树的性质不会失去.为保证在执行删除后为保证在执行删除后,树的搜索性能不至于降低树的搜索性能不至于降低,还还需要防止重新链接后树的需要防止重新链接后树的高度增加高度增加.1)删除叶结点删除叶结点,只需将其双亲结点指向它的指针清只
19、需将其双亲结点指向它的指针清零零,再释放它即可再释放它即可.2)被删结点缺右子树被删结点缺右子树,可以拿它的左子女结点顶替它可以拿它的左子女结点顶替它的位置的位置,再释放它再释放它.3)被删结点缺左子树被删结点缺左子树,可以拿它的右子女结点顶替它的可以拿它的右子女结点顶替它的位置，再释放它位置，再释放它.20第20页，共56页，编辑于2022年，星期六4)被删结点左被删结点左,右子树都存在右子树都存在,可以在它的右子树中可以在它的右子树中寻找中序下的第一个结点寻找中序下的第一个结点(关键码最小关键码最小),用它的值填用它的值填补到被删结点中补到被删结点中,再来处理这个结点的删除问题再来处理这个
20、结点的删除问题.21第21页，共56页，编辑于2022年，星期六.二叉排序树上的二叉排序树上的查找性能分析查找性能分析.二叉排序树上的查找与折半查找类似二叉排序树上的查找与折半查找类似.但但,折半查找长度为折半查找长度为n的表的判定树惟一的表的判定树惟一.显然显然,n个结点的二叉排序树的平均查找长度与树的个结点的二叉排序树的平均查找长度与树的二叉树的形态有关二叉树的形态有关.想想想想,最好情况最好情况与与最坏情况最坏情况各是各是什么样什么样?.结论结论:在随机情况下在随机情况下,二叉排序树的平均查找长度二叉排序树的平均查找长度是对数级是对数级.但这种情况出现的概率小于但这种情况出现的概率小于5
21、0%.结论结论:在构建二叉排序树的过程中要进行在构建二叉排序树的过程中要进行”平衡化平衡化”处理处理.22第22页，共56页，编辑于2022年，星期六.平衡二叉树平衡二叉树(AVL树树).AVL树的定义树的定义.一棵一棵AVL树或者是空树树或者是空树,或者是具有下列性质的二叉或者是具有下列性质的二叉搜索树搜索树:它的左子树和右子树都是它的左子树和右子树都是AVL树树,且左子树和且左子树和右子树的高度之差的绝对值不超过右子树的高度之差的绝对值不超过1.(a)(b)23第23页，共56页，编辑于2022年，星期六.结点的平衡因子结点的平衡因子.每个结点附加一个数字每个结点附加一个数字,给出该结点右
22、给出该结点右(左左)子树的高子树的高度减去左度减去左(右右)子树的高度所得的高度差子树的高度所得的高度差.这个数字即这个数字即为结点的平衡因子为结点的平衡因子balance.如果一个结点的平衡因子的绝对值大于如果一个结点的平衡因子的绝对值大于1,则这棵二则这棵二叉搜索树就失去了平衡叉搜索树就失去了平衡,不再是不再是AVL树树.任何一个结点的平衡任何一个结点的平衡因子有几个取值因子有几个取值?.一棵一棵AVL树的高度保持在什么级别树的高度保持在什么级别?.高度可保持在高度可保持在O(log2n).24第24页，共56页，编辑于2022年，星期六.平衡化处理平衡化处理.平衡化旋转有两类：平衡化旋转
23、有两类：单旋转单旋转(左旋和右旋左旋和右旋)双旋转双旋转(左平衡和右平衡左平衡和右平衡).每插入一个新结点时每插入一个新结点时,AVL树中相关结点的平衡状态会树中相关结点的平衡状态会发生改变发生改变.因此因此,在插入一个新结点后在插入一个新结点后,需要需要从插入位置从插入位置沿通向根的路径回溯沿通向根的路径回溯,检查各结点的平衡因子检查各结点的平衡因子(左左,右右子树的高度差子树的高度差).如果在某一结点发现高度不平衡如果在某一结点发现高度不平衡,停止停止回溯回溯.25第25页，共56页，编辑于2022年，星期六.从发生不平衡的结点起从发生不平衡的结点起,沿刚才回溯的路径取直接沿刚才回溯的路径
24、取直接下两层的结点下两层的结点.如果这三个结点处于一条直线上，则采用单旋转进行平如果这三个结点处于一条直线上，则采用单旋转进行平衡化衡化.单旋转可按其方向分为左单旋转和右单旋转单旋转可按其方向分为左单旋转和右单旋转,其中一个是另一个的镜像其中一个是另一个的镜像,其方向与不平衡的形状相其方向与不平衡的形状相关关.如果这三个结点处于一条折线上，则采用双旋转进行如果这三个结点处于一条折线上，则采用双旋转进行平衡化平衡化.双旋转分为先左后右和先右后左两类双旋转分为先左后右和先右后左两类.右单旋转右单旋转左单旋转左单旋转 左右双旋转左右双旋转右左双旋转右左双旋转26第26页，共56页，编辑于2022年，
25、星期六.AVL树的插入树的插入例例:输入关键码序列为输入关键码序列为 16,3,7,11,9,26,18,14,15,写出插入和调整过程写出插入和调整过程.0 0-1 1-2 20 01 1161631630 070 01 1左右双旋左右双旋左右双旋左右双旋73160 00 073110 0-1 17316161190 0-1 1-2 2右单旋右单旋右单旋右单旋371690 00 00 01 1371126916110 01 11 12 22 227第27页，共56页，编辑于2022年，星期六18180 03163-1 10 0160 02 2右左双旋右左双旋右左双旋右左双旋7390 00 0
26、0 0182611-1 1732616119-1 1左单旋左单旋左单旋左单旋9716140 00 01 1711262691 11 11128第28页，共56页，编辑于2022年，星期六15182 231816-2 2左右双旋左右双旋左右双旋左右双旋730 00 00 0117149-1 116150 01 1112626141 1-2 29例例:以以 30,35,39,15,10,28,16,29,17为例建为例建AVL树树.29第29页，共56页，编辑于2022年，星期六.动态的动态的m路搜索树路搜索树.二叉搜索树适合于组织在内存中的较小的索引二叉搜索树适合于组织在内存中的较小的索引(或目
27、或目录录),对于存放在对于存放在外存外存中的较大的文件系统中的较大的文件系统,用二叉用二叉搜索树来组织索引不太合适搜索树来组织索引不太合适.在文件检索系统中大量使用的是用在文件检索系统中大量使用的是用B-(B)树树或或B+树树做文件索引做文件索引.当数据对象数目特别大当数据对象数目特别大,索引表本身也很大索引表本身也很大,在内存中在内存中放不下放不下,需要分批多次读取外存才能把索引表搜索一遍需要分批多次读取外存才能把索引表搜索一遍.30第30页，共56页，编辑于2022年，星期六.在此情况下在此情况下,可以建立索引的索引可以建立索引的索引,称为二级索引称为二级索引.二级索引可以常驻内存二级索引
28、可以常驻内存,二级索引中一个索引项对二级索引中一个索引项对应一个索引块应一个索引块,登记该索引块的最大关键码及该索登记该索引块的最大关键码及该索引块的存储地址引块的存储地址.如果二级索引在内存中也放不下如果二级索引在内存中也放不下,需要分为许多需要分为许多块多次从外存读入块多次从外存读入.可以建立二级索引的索引，叫可以建立二级索引的索引，叫做三级索引做三级索引.这时这时,访问外存次数等于读入索引次访问外存次数等于读入索引次数再加上数再加上1次读取对象次读取对象.必要的话必要的话,还可以有还可以有4级索引级索引,5极索引极索引,.多级索引结构形成一多级索引结构形成一种种 m 叉树叉树.31第31
29、页，共56页，编辑于2022年，星期六.树中每一个树中每一个分支结点分支结点表示一个索引块表示一个索引块,它最多存放它最多存放 m 个索引项个索引项,每个索引项分别给出各子树结点每个索引项分别给出各子树结点(低一低一级索引块级索引块)的最大关键码和结点地址的最大关键码和结点地址.树的树的叶结点叶结点中各索引项给出在数据表中存放的对中各索引项给出在数据表中存放的对象的关键码和存放地址象的关键码和存放地址.这种这种m叉树用来作为多级叉树用来作为多级索引索引,就是就是m路搜索树路搜索树.m路搜索树路搜索树可能是可能是静态索引结构静态索引结构,即结构在初始创即结构在初始创建建,数据装入时就已经定型数据
30、装入时就已经定型,在整个运行期间在整个运行期间,树的结树的结构不发生变化构不发生变化.m路搜索树路搜索树还可能是还可能是动态索引结构动态索引结构,即在整个系统即在整个系统运行期间运行期间,树的结构随数据的增删及时调整树的结构随数据的增删及时调整,以保持以保持最佳的搜索效率最佳的搜索效率.32第32页，共56页，编辑于2022年，星期六多级索引结构形成多级索引结构形成 m 路搜索树路搜索树33第33页，共56页，编辑于2022年，星期六.动态的动态的 m 路搜索树路搜索树.一般定义为一般定义为:.一棵一棵 m 路搜索树路搜索树,它或者是一棵空树它或者是一棵空树,或者是满足如或者是满足如下性质的树
31、：下性质的树：根最多有根最多有 m 棵子树棵子树,并具有如下的结构：并具有如下的结构：n,P0,(K1,P1),(K2,P2),(Kn,Pn)其中，其中，Pi 是指向子树的指针是指向子树的指针,0 i n m;Ki 是是关键码关键码,1 i n m.Ki Ki+1,1 i n.在子树在子树 Pi 中所有的关键码都中所有的关键码都小于小于 Ki+1，且，且大于大于 Ki,0 i n.在子树在子树 Pn 中所有的关键码都中所有的关键码都大于大于Kn.在子树在子树 P0 中的所有关键码都中的所有关键码都小于小于 K1.子树子树 Pi 也是也是 m 路搜索树路搜索树,0 i n.34第34页，共56页
32、，编辑于2022年，星期六.一棵一棵3路搜索树的示例路搜索树的示例.AVL树是树是m=?路搜索树路搜索树?35第35页，共56页，编辑于2022年，星期六.B-树树.一棵一棵 m 阶阶B_树是一棵树是一棵 m 路搜索树路搜索树,它或者是空树它或者是空树,或者是满足下列性质的树或者是满足下列性质的树:.根结点根结点至少有至少有 2 个子女个子女.除根结点以外的所有结点除根结点以外的所有结点(不包括失败结点不包括失败结点)至少有至少有 m/2 个子女个子女.所有的失败结点都位于同一层所有的失败结点都位于同一层.事实上事实上,在在B-树的树的每个结点每个结点中还包含有一组指针中还包含有一组指针Dm,
33、指向实际对象的存放地址指向实际对象的存放地址.Ki与与Di(1 i n m)形成一个索引项形成一个索引项(Ki,Di).通过通过Ki可找到某可找到某个对象的存储地址个对象的存储地址Di.36第36页，共56页，编辑于2022年，星期六.非非B-树与树与B-树的示例图树的示例图非非B-树树B-树树.B-树上的树上的搜索搜索37第37页，共56页，编辑于2022年，星期六.B-树的搜索过程是一个在树的搜索过程是一个在结点内搜索结点内搜索和和循某一条路循某一条路径向下一层搜索径向下一层搜索交替进行的过程交替进行的过程.因此因此,B-树的搜索树的搜索时间与时间与B-树的阶数树的阶数m和和B-树的高度树
34、的高度h直接有关直接有关,必须必须加以权衡加以权衡.在在B-树上进行搜索树上进行搜索,搜索成功搜索成功所需的时间取决于关所需的时间取决于关键码所在的键码所在的层次层次,搜索不成功搜索不成功所需的时间取决于所需的时间取决于树树的高度的高度.在在B-树上搜索的示例树上搜索的示例38第38页，共56页，编辑于2022年，星期六.B-树上的树上的插入插入.B-树是从空树起树是从空树起,逐个插入关键码而生成的逐个插入关键码而生成的.在在B-树树,每个非失败结点的关键码个数都在每个非失败结点的关键码个数都在 m/2 -1,m-1之间之间.插入在插入在某个叶结点某个叶结点开始开始.如果在关键码插入后结点如果
35、在关键码插入后结点中的关键码个数超出了上界中的关键码个数超出了上界 m-1,则结点需要则结点需要“分裂分裂”,否则可以直接插入否则可以直接插入.实现实现“分裂分裂”的原则的原则39第39页，共56页，编辑于2022年，星期六.设结点设结点 p 中已经有中已经有 m-1个关键码个关键码,当再插入一个关当再插入一个关键码后结点中的状态为键码后结点中的状态为:.(m,P P0 0,K1 1,P P1 1,K K2 2,P P2 2,Kmm,Pmm)其中其中 K Ki Ki+1,1,1 i i mm 这时必须把结点这时必须把结点这时必须把结点这时必须把结点 p p分裂成两个结点分裂成两个结点分裂成两个
36、结点分裂成两个结点 p p和和和和q,q,它们包含的信息分它们包含的信息分它们包含的信息分它们包含的信息分别为：别为：别为：别为：结点结点结点结点 p p：(mm/2/2 -1,-1,P P0 0,K K1 1,P P1 1,K K mm/2/2 -1,P mm/2 -1)1)结点结点结点结点 q q：(mm-m/2 ,P P mm/2 ,K mm/2/2 +1+1,P P mm/2/2 +1+1,K Kmm,P Pmm)位于中间的关键码位于中间的关键码位于中间的关键码位于中间的关键码 K m/2 与指向新结点与指向新结点与指向新结点与指向新结点 q q 的指针形成一个的指针形成一个的指针形成
37、一个的指针形成一个二元组二元组二元组二元组 (K K mm/2/2 ,q),q),插入到这两个结点的插入到这两个结点的插入到这两个结点的插入到这两个结点的双亲结点双亲结点双亲结点双亲结点中去中去中去中去.40第40页，共56页，编辑于2022年，星期六结点结点“分裂分裂”的示例的示例41第41页，共56页，编辑于2022年，星期六.B-树上的树上的插入示例插入示例:从空树开始逐个加入关键码从空树开始逐个加入关键码53,75,139,49,145,36,101建立建立3阶阶B-树树.42第42页，共56页，编辑于2022年，星期六.若设若设B-树的高度为树的高度为h.那么在那么在自顶向下自顶向下
38、搜索到搜索到叶结点叶结点的过程中需要进行的过程中需要进行h次读盘次读盘.在插入新关键码时在插入新关键码时,需要自底向上分裂结点需要自底向上分裂结点,最坏情最坏情况下从被插关键码所在叶结点到根的路径上的所有结况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂点都要分裂.43第43页，共56页，编辑于2022年，星期六.B-树上的树上的删除删除.在在B-树上删除一个关键码时树上删除一个关键码时,首先需要找到这个首先需要找到这个关键码所在的结点关键码所在的结点,从中删去这个关键码从中删去这个关键码.若该结点不是叶结点若该结点不是叶结点,且被删关键码为且被删关键码为 Ki,1 i n,则在删去该
39、关键码之后则在删去该关键码之后,应以该结点应以该结点 Pi 所指示子所指示子树中的最小关键码树中的最小关键码x来代替被删关键码来代替被删关键码 Ki 所在的位置所在的位置,然后在然后在x所在的叶结点中删除所在的叶结点中删除 x.在叶结点上删除有在叶结点上删除有4种情况种情况:1)被删关键码所在叶结点同时又是根结点且删除被删关键码所在叶结点同时又是根结点且删除前该结点中关键码个数前该结点中关键码个数 n 2,则直接删去该关键码则直接删去该关键码并将修改后的结点写回磁盘并将修改后的结点写回磁盘.44第44页，共56页，编辑于2022年，星期六2)被删关键码所在叶结点不是根结点且删除前该结被删关键码
40、所在叶结点不是根结点且删除前该结点中关键码个数点中关键码个数 n m/2,则直接删去该关键码并将则直接删去该关键码并将修改后的结点写回磁盘修改后的结点写回磁盘,删除结束删除结束.45第45页，共56页，编辑于2022年，星期六3)被删关键码所在叶结点删除前关键码个数被删关键码所在叶结点删除前关键码个数 n=m/2 -1,若若这时与该结点相邻的右兄弟这时与该结点相邻的右兄弟(或左兄弟或左兄弟)结点的关键码个数结点的关键码个数 n m/2，则可按以下步骤调整该结点，则可按以下步骤调整该结点,右兄弟右兄弟(或左兄弟或左兄弟)结点以及其双亲结点结点以及其双亲结点,以达到新的平衡。以达到新的平衡。.将双
41、亲结点中刚刚大于将双亲结点中刚刚大于(或小于或小于)该被删关键码的关键码该被删关键码的关键码 Ki (1 i n)下移；下移；.将右兄弟将右兄弟(或左兄弟或左兄弟)结点中的最小结点中的最小(或最大或最大)关键码上关键码上移到双亲结点的移到双亲结点的 Ki 位置；位置；.将右兄弟将右兄弟(或左兄弟或左兄弟)结点中的最左结点中的最左(或最右或最右)子树指针平子树指针平移到被删关键码所在结点中最后移到被删关键码所在结点中最后(或最前或最前)子树指针位置；子树指针位置；.在右兄弟在右兄弟(或左兄弟或左兄弟)结点中结点中,将被移走的关键码和指针将被移走的关键码和指针位置用剩余的关键码和指针填补位置用剩余
42、的关键码和指针填补,调整调整.再将结点中的关键再将结点中的关键码个数减码个数减1.46第46页，共56页，编辑于2022年，星期六47第47页，共56页，编辑于2022年，星期六48第48页，共56页，编辑于2022年，星期六4)被删关键码所在叶结点删除前关键码个数被删关键码所在叶结点删除前关键码个数n=m/2 -1,若这时若这时与该结点相邻的右兄弟与该结点相邻的右兄弟(或左兄弟或左兄弟)结点的关键码个数结点的关键码个数 n=m/2 -1,则必须按以下步骤合并这两个结点则必须按以下步骤合并这两个结点.将将双亲结点双亲结点 p 中相应关键码下移到选定保留的结点中中相应关键码下移到选定保留的结点中
43、.若要合并若要合并 p 中的子树指针中的子树指针 Pi 与与 Pi+1 所指的结点所指的结点,且保留且保留 Pi 所所指结点指结点,则把则把 p 中的关键码中的关键码 Ki+1下移到下移到 Pi 所指的结点中所指的结点中.把把 p 中子树指针中子树指针 Pi+1 所指结点中的全部指针和关键码都所指结点中的全部指针和关键码都照搬到照搬到 Pi 所指结点的后面所指结点的后面.删去删去 Pi+1 所指的结点所指的结点.在结点在结点 p中用后面剩余的关键码和指针填补关键码中用后面剩余的关键码和指针填补关键码 Ki+1 和和指针指针 Pi+1.修改结点修改结点 p和选定保留结点的关键码个数和选定保留结点
44、的关键码个数.在合并结点的过程中在合并结点的过程中,双亲结点中的关键码个数减少双亲结点中的关键码个数减少了了.49第49页，共56页，编辑于2022年，星期六.若双亲结点是根结点且结点关键码个数减到若双亲结点是根结点且结点关键码个数减到 0，则该，则该双亲结点应从树上删去双亲结点应从树上删去,合并后保留的结点成为新的合并后保留的结点成为新的根结点根结点;否则将双亲结点与合并后保留的结点都写回否则将双亲结点与合并后保留的结点都写回磁盘磁盘,删除处理结束删除处理结束.若双亲结点不是根结点若双亲结点不是根结点,且关键码个数减到且关键码个数减到 m/2 -2,又又要与它自己的兄弟结点合并要与它自己的兄弟结点合并,重复上面的合并步骤重复上面的合并步骤.最坏情况下这种结点合并处理要自下向上直到根结最坏情况下这种结点合并处理要自下向上直到根结点点.50第50页，共56页，编辑于2022年，星期六51第51页，共56页，编辑于2022年，星期六52第52页，共56页，编辑于2022年，星期六53第53页，共56页，编辑于2022年，星期六54第54页，共56页，编辑于2022年，星期六55第55页，共56页，编辑于2022年，星期六56第56页，共56页，编辑于2022年，星期六