[工学]数据结构第17次课-查找C课件.ppt

1、数据结构计算机与信息学院 姜敏 第1页 1.上机实现顺序查找的改进算法。上机实现顺序查找的改进算法。2.上机实现折半查找的递归及非递归算法。上机实现折半查找的递归及非递归算法。选做：选做：3.设计一个算法，利用折半查找算法在一个设计一个算法，利用折半查找算法在一个 有序表中插入一个元素有序表中插入一个元素x，并保持表的有序，并保持表的有序 性，上机实现。性，上机实现。实验三实验三数据结构计算机与信息学院 姜敏 第2页针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有：8.2 8.2 静态查找表静态查找表一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找

2、）折半查找（二分或对分查找）三、静态树表的查找三、静态树表的查找四、四、分块查找（索引顺序查找）分块查找（索引顺序查找）上节课内容回顾数据结构计算机与信息学院 姜敏 第3页一、顺序查找（一、顺序查找（Linear searchLinear search，又称线性查找又称线性查找 ）顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。v对对顺序结构顺序结构如何线性查找？如何线性查找？挨个比较挨个比较v对对单链表结构单链表结构如何线性查找？函数虽未给出，但也很容易编如何线性查找？函数虽未给出，但也很容易编写；只要知道头

3、指针写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v对对非线性树结构非线性树结构如何顺序查找如何顺序查找?可借助各种可借助各种遍历遍历操作！操作！优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点：ASL(n+1)/2,ASL太大，时间效率太低。太大，时间效率太低。顺序查找的特点：顺序查找的特点：数据结构计算机与信息学院 姜敏 第4页二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查找）先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keyke

4、y与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其小，则缩小至右半部内查找；再取其中值比较，每次缩小中值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。low=1；high=length；/设置初始区间 当lowhigh时，返回查找失败信息 /表空，查找失败 lowhigh，mid=(low+high)/2;/取中点 a.若kxelemmid.key，low=mid+1；转 /查找在右半区进行 c.若kx=elemmid.key，返回数据元素在表中位置 /查找成功 数据结构计算机与信息学院 姜敏 第5页四、分块查找（索引

5、顺序查找）四、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。这是一种顺序查找的另一种改进方法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。必有序）。然后将各子表中的最大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要，表中还要包含每个子表的起始地址（即头指针）。包含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址22 12 138920 33 42 44 38 24 48 6

6、0 58 74 49 86 53第第1 1块块第第2 2块块第第3 3块块224886例：例：2248861713特点：块间有特点：块间有序，块内无序序，块内无序数据结构计算机与信息学院 姜敏 第6页查找步骤查找步骤分两步进行：分两步进行：对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对

7、块内查找的ASL)21(log2)1(log22nASLnssnASLbsbsS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时时，ASLASLbsbs=3.53.5,而折半法为而折半法为3.13.1,顺序法为顺序法为5 5数据结构计算机与信息学院 姜敏 第7页ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表三种静态查找方法比较三种静态查找方法比较顺

8、序查找顺序查找折半查找折半查找分块查找分块查找小结小结：数据结构计算机与信息学院 姜敏 第8页针对动态查找表的查找算法主要有：针对动态查找表的查找算法主要有：8.3 8.3 动态查找表动态查找表一、二叉排序树（一、二叉排序树（BST）二、平衡二叉树（二、平衡二叉树（AVL树）树）三、三、B-、B+树树数据结构计算机与信息学院 姜敏 第9页1 1、二叉排序树的定义回顾、二叉排序树的定义回顾-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树：（1 1）左左子树的所有结点均子树的所有结点均小小于根的值；于根的值；（2 2）右右子树的所有结点均子树的所有结点均

9、大大于根的值；于根的值；（3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。递归定义递归定义 （4 4）其中序遍历序列为一个递增序列其中序遍历序列为一个递增序列 一一.二叉排序树搜索二叉排序树搜索数据结构计算机与信息学院 姜敏 第10页2 2、二叉排序树的插入与删除、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点：查找过程与顺序结构有序表中的查找过程与顺序结构有序表中的折半查找折半查找相似，查找效率高；相似，查找效率高；如果查找不成功，能够方便地将被查元素如果查找不成功，能够方便地将被查元素插入到二叉树的叶子插入到二叉树的叶子结

10、点结点上，而且插入或删除时只需修改指针而不需移动元素。上，而且插入或删除时只需修改指针而不需移动元素。注：注：若若数据元素的数据元素的输入顺序不同，则得到的二叉排序树形态输入顺序不同，则得到的二叉排序树形态也不同！也不同！这种既查找又插入的过程称为这种既查找又插入的过程称为动态查找动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。储，它是动态查找表的一种适宜表示。数据结构计算机与信息学院 姜敏 第11页45452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入

11、顺序为：（2424，5353，4545，4545，1212，2424，9090）24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回讨论讨论1 1：二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列=（4545，2424，5353，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同序树形态不同：查查找找成成功功返返回回查查找找成成功功返返回回数据结构计算机与信息学院 姜敏 第12页bstnode BSTSEARCH

12、(bstnode t,keytype k)bstnode p;p=t;while(p)if(p.key=k)return p;if(p.key k)p=p.lchild;else p=p.rchild;return NULL;1.二叉排序树的查找二叉排序树的查找452453122890二叉排序树的二叉排序树的查找查找&插入插入算法如何实现？算法如何实现？数据结构计算机与信息学院 姜敏 第13页2.二叉排序树的结点插二叉排序树的结点插入入452453122890a.a.若原树为空，返回若原树为空，返回以新插入结点为树根的树以新插入结点为树根的树。b.否则，找到要插入的父结点。否则，找到要插入的父

13、结点。c.将新结点插入确定位置将新结点插入确定位置474745,4745,向右子树搜索向右子树搜索4753,4753,向左子树搜索向左子树搜索5353左子树为空，左子树为空，4747应该插入到此处应该插入到此处,47数据结构计算机与信息学院 姜敏 第14页bstnode INSERTBST(bstnode t,bstnode s)bstnode f,p;p=t;if(t=NULL)return s;/原树原树t为空为空 while(p!=NULL)/找插入父结点找插入父结点 f=p;/保存当前节点指针保存当前节点指针 if(s.key=p.key)return t;/s在在t中已经存在中已经存

14、在 if(s.keyp.key)p=p.lchild;/比当前结点小，向左比当前结点小，向左 else p=p.rchild;/比当前结点大，向右比当前结点大，向右 if(s.keyf.key)f.lchild=s;/找插入父结点找插入父结点,插入确定位置插入确定位置 else f.rchild=s;return t;二叉排序树的结点插入算法二叉排序树的结点插入算法数据结构计算机与信息学院 姜敏 第15页对于二叉排序树，删除树上一个结点相当于删除有序序列中对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。的一个记录，删除后仍需保持二叉排序树的特性。

15、（对链表进行删除操作是很方便的）（对链表进行删除操作是很方便的）具体算法参看树具体算法参看树D D课件课件讨论讨论2 2：二叉排序树的删除操作：二叉排序树的删除操作数据结构计算机与信息学院 姜敏 第16页1)1)二叉排序树上查找某关键字等于给定值的结点过二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。程，其实就是走了一条从根到该结点的路径。比较的关键字次数比较的关键字次数此结点的层次数此结点的层次数;最多的比较次数最多的比较次数树的深度（或高度），即树的深度（或高度），即 loglog2 2 n n+1+12)2)一棵二叉排序树的平均查找长度为：一棵二叉排序树

16、的平均查找长度为：3.3.二叉排序树的查找分析二叉排序树的查找分析其中：其中：n ni i 是每层结点个数；是每层结点个数；c ci i 是结点所在层次数；是结点所在层次数；m m 为树深。为树深。11ASLmiiincn数据结构计算机与信息学院 姜敏 第17页最坏情况：最坏情况：即插入的即插入的n个元素从一开始就有序，个元素从一开始就有序，变成单支树的形态！变成单支树的形态！此时树的深度为此时树的深度为n ;ASL=(n+1)/2 此时查找效率与顺序查找情况相同。此时查找效率与顺序查找情况相同。最好情况最好情况：即：与折半查找中的判定树相同（形态比较均衡）：即：与折半查找中的判定树相同（形态

17、比较均衡）树的深度为：树的深度为：log 2n +1；ASL=(n+1)/n*log 2(n+1)1；与折半查找相同。；与折半查找相同。数据结构计算机与信息学院 姜敏 第18页3）对有）对有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度:设每种树态出现概率相设每种树态出现概率相 同同，查找每个关键字也，查找每个关键字也是等概率的。是等概率的。则则ASL求解过程可推导。求解过程可推导。结论：二叉排序树的结论：二叉排序树的ASL2（11/n）ln n问：如何能让二叉排序树的查找过程保持最好情况？问：如何能让二叉排序树的查找过程保持最好情况？数据结构计算机与信息学院 姜敏

18、 第19页二 平衡二叉树(AVL树）什么是平衡二叉树什么是平衡二叉树(Balanced Binary TreeBalanced Binary Tree)?平衡二叉树是空树平衡二叉树是空树,或者是具有以下性质的二叉树或者是具有以下性质的二叉树:它的左子树和右子树也都是它的左子树和右子树也都是平衡二叉树并且平衡二叉树并且左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过1 1结点的结点的平衡因子平衡因子BFBF (Balance Factor)(Balance Factor)是是左子树的深度减去右子树的深度左子树的深度减去右子树的深度,它只可能是它只可能是 -1,0,1-

19、1,0,1平衡二叉树平衡二叉树(也称也称AVLAVL树树)的深度为的深度为O(logO(log2 2N)N)(其中其中N N为结点个数为结点个数)它的平均查找长度也是它的平均查找长度也是O(logO(log2 2N)N)数据结构计算机与信息学院 姜敏 第20页平衡二叉树及平衡因子举例-1100-110平衡的二叉树平衡的二叉树1100数据结构计算机与信息学院 姜敏 第21页不平衡的二叉树不平衡的二叉树-1000-210 2 2-101 00不平衡二叉树及平衡因子举例危急危急结点结点危急危急结点结点数据结构计算机与信息学院 姜敏 第22页二叉排序树在结点添加过程中失衡二叉排序树在结点添加过程中失衡

20、的几种情况的几种情况LLRRLRRL2a1b0c0c0c0c-1b-1b1b-2a2a-2a数据结构计算机与信息学院 姜敏 第23页二叉排序树转成平衡树失去平衡后需要进行调整的四种情况(1)单向右旋平衡处理LL当在左子树上插入左结点,使平衡因子由1增至2时(2)单向左旋平衡处理RR当在右子树上插入右结点,使平衡因子由-1增至-2时(3)双向旋转(先左后右)平衡处理LR当在左子树上插入右结点,使平衡因子由1增至2时(4)双向旋转(先右后左)平衡处理RL当在右子树上插入左结点,使平衡因子由-1增至-2时数据结构计算机与信息学院 姜敏 第24页2A1B0A0BBLBRARhh-1h-1ARBRLLB

21、L 1、LL型平衡旋转型平衡旋转 A的的左子树的左子树左子树的左子树上插入结点，作顺时针旋转。上插入结点，作顺时针旋转。数据结构计算机与信息学院 姜敏 第25页2、RR型：型：A的的右子树右子树的的右子树右子树上插入结点，作逆时针旋转。上插入结点，作逆时针旋转。-2A-1B0A0BBRBLALh-1BLALRRBRh-1h数据结构计算机与信息学院 姜敏 第26页2A-1B-1A0CCLBLARh-2h-1h-1LR1Ch-1CR0BBLARCLCR3、LR型：型：A的的左子树左子树的的右子树右子树上插入结点，作两次（逆、顺）旋转。上插入结点，作两次（逆、顺）旋转。数据结构计算机与信息学院 姜敏

22、 第27页4 RL型：型：在在A的右子树的左子树上插入结点，作两次（顺、逆）旋转。的右子树的左子树上插入结点，作两次（顺、逆）旋转。h-1-2A1B-1B0CCLALh-2h-1RL1Ch-1CR0AALBRCLCRBR数据结构计算机与信息学院 姜敏 第28页二叉排序树在结点添加平衡化方法总结LLRRLRRL2a1b0c0c0c0c-1b-1b1b-2a2a-2a0a0b0c0a0b0c0b0c0a0a0c0b数据结构计算机与信息学院 姜敏 第29页二叉排序树转成平衡树示例二叉排序树转成平衡树示例设关键字序列为设关键字序列为(13,24,37,90,53)(13,24,37,90,53)013

23、-113 024 037 013-213-124 024 037 053 013 013 037 090 053-124 190-237-224(a)(b)(c)(d)(e)(f)(g)(h)2413375390(h)2413375390数据结构计算机与信息学院 姜敏 第30页练习：下列情况属于哪种失衡状况？应该操作哪些结点？练习：下列情况属于哪种失衡状况？应该操作哪些结点？-21207-119122020016LR 12,7,9RR 12,19212-17019190806数据结构计算机与信息学院 姜敏 第31页二叉排序树在结点添加平衡化实例二叉排序树在结点添加平衡化实例例：给定平衡二叉排序

24、树的输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，601501211501201507-112-1150701911221507数据结构计算机与信息学院 姜敏 第32页例：给定平衡二叉排序树的输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，6-212-21507-119024-11201507019024112015-270190241908012015-1701902409数据

25、结构计算机与信息学院 姜敏 第33页例：给定平衡二叉排序树的输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，601201507019024090811201517019024091805212015270190240928-15061120150701902409180506数据结构计算机与信息学院 姜敏 第34页失衡二叉排序树平衡化过程特性失衡二叉排序树平衡化过程特性h-1-2A1B-1B0CCLALh-2h-1RL1Ch-1CR0AALBRCLCRBR 1、树的高度不会增加；树的高度

26、不会增加；h1 2、保持了二叉排序树的基本性质。保持了二叉排序树的基本性质。3、使二叉排序查找性能趋近二分查找。使二叉排序查找性能趋近二分查找。数据结构计算机与信息学院 姜敏 第35页 在平衡树上进行查找的过程和二叉排序树相同，因在平衡树上进行查找的过程和二叉排序树相同，因此此在查找过程中和给定值进行比较的关键码个数不超过在查找过程中和给定值进行比较的关键码个数不超过树的深度。为了确定含有树的深度。为了确定含有n n个关键码的平衡树的最大深个关键码的平衡树的最大深度，先分析深度为度，先分析深度为h h的平衡树所具有的最少结点数的平衡树所具有的最少结点数。平衡二叉树查找性能分析平衡二叉树查找性能

27、分析(查找插入平衡化）查找插入平衡化）斐波那契序列斐波那契序列：F F0 00 0，F F1 11 1，F Fi iF Fi-1i-1+F+Fi-2i-2F F0 00 0，F F1 11 1，F F2 21,F1,F3 3=2,=2,F F4 4=3,F=3,F5 5=5,F=5,F6 6=8,F=8,F7 7=13,F=13,F8 82121数据结构计算机与信息学院 姜敏 第36页 假设以假设以N Nh h表示深度为表示深度为h h的平衡树中含有的最少结的平衡树中含有的最少结点数。显然，点数。显然，N N0 0=0=0，N N1 1=1=1，N N2 2=2=2，并且并且N Nh h=N=

28、Nh-1h-1+N+Nh-2h-2+1+1。这个关系和斐波那契序列极为相似。利用归纳法。这个关系和斐波那契序列极为相似。利用归纳法容易证明：当容易证明：当h0.h0.因此，在平衡二叉树上进行查找的时间复杂度为因此，在平衡二叉树上进行查找的时间复杂度为O(logO(log2 2n)n)。问：问：深度为深度为6 6的平衡树最少具有的平衡树最少具有多少多少结点结点？20数据结构计算机与信息学院 姜敏 第37页 平衡树以二叉链表作为存储结构平衡树以二叉链表作为存储结构,每个结点还要每个结点还要增加增加一个平衡因子域一个平衡因子域。平衡树的平衡树的查找运算与普通树型查找完全相同查找运算与普通树型查找完全

29、相同，由于平，由于平衡树附加了平衡条件，其高度与结点数相同的完全树衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。属于同一数量级，所以有较快的查找速度。在插入新结点时，当确定了新结点应插入的位置后，在插入新结点时，当确定了新结点应插入的位置后，需向上寻找有关平衡因子变为需向上寻找有关平衡因子变为+2+2或或-2-2的祖先的祖先，如有这，如有这种结点，则取种结点，则取其中层数居最低者其中层数居最低者，根据不同的情况进，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的

30、平衡因子加以修每次插入结点后，还需对有关祖先的平衡因子加以修改改。平衡二叉排序树编程实现注意事项平衡二叉排序树编程实现注意事项数据结构计算机与信息学院 姜敏 第38页v B-树的形态和本质树的形态和本质三 B、B+树111351118127199645334778432139FFFFFFFFFFFF本质：本质：多路查找树多路查找树，查找过程类似于二叉排序树，查找过程类似于二叉排序树非终端结点非终端结点中包含下列信息数据（中包含下列信息数据（n，A0，K1，A1，K2，A2，Kn，An）数据结构计算机与信息学院 姜敏 第39页v B-树的定义树的定义或曰性质或曰性质 一棵一棵m阶的阶的B-树树，

31、或为空树，或为满足下列特性的，或为空树，或为满足下列特性的m叉树：叉树：1、树中每个结点树中每个结点至多至多有有m棵子棵子树；树；2、若根结点若根结点不是叶子结点，则不是叶子结点，则至少至少有两棵子树；有两棵子树；3、除根之外的除根之外的所有非终端结点至少有所有非终端结点至少有 m/2 棵子树；棵子树；4、所有的非终端结点所有的非终端结点中包含下列信息数据（中包含下列信息数据（n，A0，K1，A1，K2，A2，Kn，An），其中），其中Ki为关键字，为关键字，关键字关键字个数个数n 必须满足必须满足 m/2 1=n=m-1。5、所有的叶子结点都出现在同一层次上，并且不带信息。所有的叶子结点都出

32、现在同一层次上，并且不带信息。数据结构计算机与信息学院 姜敏 第40页例：一棵四阶的例：一棵四阶的B-树。树。111351118127199645334778432139FFFFFFFFFFFF11bt3543,7818 2739 99 47,53,64数据结构计算机与信息学院 姜敏 第41页B-树的插入（要求保持树的插入（要求保持B-树性质不变）树性质不变）B-树的生成也是从空树起，逐个插入关键字而得。但由于树的生成也是从空树起，逐个插入关键字而得。但由于B-树结点中得关键字个数必须树结点中得关键字个数必须m/2-1，因此，每次插入一个关键，因此，每次插入一个关键字不是在树中添加一个叶子接点

33、，而是首先在最低层的某个非终字不是在树中添加一个叶子接点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数端结点中添加一个关键字，若该结点的关键字个数不超过不超过m-1，则插入完成，否则要产生结点的则插入完成，否则要产生结点的分裂分裂。例：例：在下面是一棵在下面是一棵3 3阶的阶的B B-树，从中插入元素树，从中插入元素3030，2626，8585。3 12bt4553 9024 3750 100 61 70 数据结构计算机与信息学院 姜敏 第42页3 12bt4553 9024 30 3750 100 61 70 插入元素插入元素30 3 12bt45 53 9024

34、26 30 3750 100 61 70 插入元素插入元素26数据结构计算机与信息学院 姜敏 第43页3 12bt45 53 9024 30 3750 100 61 70 插入元素插入元素26263 12bt4553 9024 30 3750 100 61 70 85 插入元素插入元素85 26数据结构计算机与信息学院 姜敏 第44页 插入元素插入元素85bt45 703 12905324 30372650 100 85 61 3 12bt4553 70 9024 3750 100 85 61问：此时插入关键字问：此时插入关键字7 7，如何改变树结构？动手练习一下！，如何改变树结构？动手练习一

35、下！数据结构计算机与信息学院 姜敏 第45页B-树的删除树的删除 若在若在B-树中删除一个关键字，则首先应找到该关键字所在树中删除一个关键字，则首先应找到该关键字所在结点，并丛中删除之。结点，并丛中删除之。若该结点为若该结点为最下层的非终端结点最下层的非终端结点，且其中的关键字数目不，且其中的关键字数目不小于小于 m/2，则删除完成，否则进行，则删除完成，否则进行“合并合并”结点的操作。结点的操作。3 12bt45 53 9024 30 3750 100 61 70 26直接删除元素直接删除元素61数据结构计算机与信息学院 姜敏 第46页假若所删除关键字为非终端结点中的假若所删除关键字为非终端

36、结点中的Ki，则可以指针则可以指针Ai所指子树中的最所指子树中的最小关键字小关键字Y替代替代Ki，然后在相应的结点中删除，然后在相应的结点中删除Y。删除元素删除元素243 12bt45 53 9024 30 3750 100 61 70 263 12bt45 53 9026 30 3750 100 61 70 26删除终端结点删除终端结点数据结构计算机与信息学院 姜敏 第47页因此，下面我们可以只需讨论因此，下面我们可以只需讨论删除最下层非终端结点中的关键字删除最下层非终端结点中的关键字的情形的情形。有下面三种可能：。有下面三种可能：1、被删除关键字所在结点中的关键字数目、被删除关键字所在结点

37、中的关键字数目不小于不小于 m/2，则只，则只需从该结点中删去该关键字需从该结点中删去该关键字Ki和相应指针和相应指针Ai，树的其它部分不变。，树的其它部分不变。2、被删除关键字所在结点的关键字数目、被删除关键字所在结点的关键字数目等于等于 m/2-1，而与该，而与该结点相邻的结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于右兄弟（或左兄弟）结点中的关键字数目大于 m/2-1，则只需将其右兄弟结点中的最小（或左兄弟结点中的最大）的关则只需将其右兄弟结点中的最小（或左兄弟结点中的最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠键字上移至双亲结点中，而将双亲结点中小于（或大于）

38、且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。该上移关键字的关键字下移至被删除关键字所在结点中。数据结构计算机与信息学院 姜敏 第48页3 12bt45 53 9024 30 3750 100 61 70 26删除终端结点删除终端结点503 12bt45 61 9024 30 3753 100 70 26数据结构计算机与信息学院 姜敏 第49页 3、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 m/2-1。若该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针。若该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针

39、Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字亲结点中的关键字Ki一起，合并到一起，合并到Ai所指兄弟结点中（若没有右兄弟，则合所指兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。并到左兄弟结点中）。12bt45 53 9025 30 3750 100 61 70 26删除终端结点删除终端结点2612bt45 53 9025 30 3750 100 61 70 数据结构计算机与信息学院 姜敏 第50页v B+树的定义树的定义 B+树是文件系统所需而出的一种树是文件系统所需而出的一种B-树的变

40、型树。一棵树的变型树。一棵m阶的阶的B+树和树和m阶的阶的B-树的区别在于：树的区别在于：1、有、有n棵子树的结点汇总含有棵子树的结点汇总含有n个关键字。个关键字。2、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小而大顺序链接。字记录的指针，且叶子结点本身依关键字的大小而大顺序链接。3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根、所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。结点）中的最大（或最小）关键字。在在B+树上进行随机查找、插入和删除的过程与树上进行随机查找、插入和删除的过程与B-树基本类似，在此不树基本类似，在此不做详细的介绍。做详细的介绍。