工学数据结构查找C培训课件.ppt

《工学数据结构查找C培训课件.ppt》由会员分享，可在线阅读，更多相关《工学数据结构查找C培训课件.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构计算机与信息学院 姜敏 工学数据结构查找C数据结构计算机与信息学院 姜敏 一、顺序查找（一、顺序查找（Linear searchLinear search，又称线性查找又称线性查找 ）顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。v对对顺序结构顺序结构如何线性查找？如何线性查找？挨个比较挨个比较v对对单单链链表表结结构构如如何何线线性性查查找找？函函数数虽虽未未给给出出，但但也也很很容容易易编编写；只要知道头指针写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v对对非线性树结构非线

2、性树结构如何顺序查找如何顺序查找?可借助各种可借助各种遍历遍历操作！操作！优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点：ASL(n+1)/2,ASL太大，时间效率太低。太大，时间效率太低。顺序查找的特点：顺序查找的特点：2数据结构计算机与信息学院 姜敏 二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查找）先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其小，则缩小至右半

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

4、法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。必有序）。然后将各子表中的最大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要，表中还要包含每个子表的起始地址（即头指针）。包含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53第第1 1块块第第2 2块块第第3 3块块224886例：例：2248

5、861713特点：块间有特点：块间有序，块内无序序，块内无序4数据结构计算机与信息学院 姜敏 查找步骤查找步骤分两步进行：分两步进行：对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASLS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9

6、n=9，s=3s=3时时，ASLASLbsbs=3.53.5,而折半法为而折半法为3.13.1,顺序法为顺序法为5 55数据结构计算机与信息学院 姜敏 ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表三种静态查找方法比较三种静态查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找小结小结：6数据结构计算机与信息学院 姜敏 针对动态查找表的查找算法主要有：针对动态查找表的查找算法主要有：8.3 8.3 动

7、态查找表动态查找表一、二叉排序树（一、二叉排序树（BST）二、平衡二叉树（二、平衡二叉树（AVL树）树）三、三、B-、B+树树7数据结构计算机与信息学院 姜敏 1 1、二叉排序树的定义二叉排序树的定义回顾回顾-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树：（1 1）左左子树的所有结点均子树的所有结点均小小于根的值；于根的值；（2 2）右右子树的所有结点均子树的所有结点均大大于根的值；于根的值；（3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。递归定义递归定义 （4 4）其中序遍历序列为一个递增序列其中序遍历序列为一个递增序

8、列 一一.二叉排序树二叉排序树搜索搜索8数据结构计算机与信息学院 姜敏 2 2、二叉排序树的插入与删除、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点：查找过程与顺序结构有序表中的查找过程与顺序结构有序表中的折半查找折半查找相似，查找效率高；相似，查找效率高；如果查找不成功，能够方便地将被查元素如果查找不成功，能够方便地将被查元素插入到二叉树的叶子插入到二叉树的叶子结点结点上，而且插入或删除时只需修改指针而不需移动元素。上，而且插入或删除时只需修改指针而不需移动元素。注：注：若若数据元素的数据元素的输入顺序不同，则得到的二叉排序树形态输入顺序不同，则得

9、到的二叉排序树形态也不同！也不同！这种既查找又插入的过程称为这种既查找又插入的过程称为动态查找动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。储，它是动态查找表的一种适宜表示。9数据结构计算机与信息学院 姜敏 45452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入顺序为：（2424，5353，45 45，4545，1212，2424，9090）24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回讨论讨论1 1：

10、二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列=（4545，2424，5353，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同序树形态不同：查查找找成成功功返返回回查查找找成成功功返返回回10数据结构计算机与信息学院 姜敏 bstnode BSTSEARCH(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.rchi

11、ld;return NULL;1.二叉排序树的查找二叉排序树的查找452453122890二叉排序树的二叉排序树的查找查找&插入插入算法如何实现？算法如何实现？11数据结构计算机与信息学院 姜敏 2.二叉排序树的结点插入二叉排序树的结点插入452453122890a.a.若原树为空，返回若原树为空，返回以新插入结点为树根的树以新插入结点为树根的树。b.否则，找到要插入的父结点。否则，找到要插入的父结点。c.将新结点插入确定位置将新结点插入确定位置474745,4745,向右子树搜索向右子树搜索4753,4753,向左子树搜索向左子树搜索5353左子树为空，左子树为空，4747应该插入到此处应该

12、插入到此处,4712数据结构计算机与信息学院 姜敏 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中已经存在中已经存在 if(s.keyp.key)p=p.lchild;/比当前结点小，向左比当前结点小，向左 else p=p.rchild;/比当前结点大，向右比当前结点大，向右 if(s.keyf.key)f.lch

13、ild=s;/找插入父结点找插入父结点,插入确定位置插入确定位置 else f.rchild=s;return t;二叉排序树的结点插入算法二叉排序树的结点插入算法13数据结构计算机与信息学院 姜敏 对于二叉排序树，删除树上一个结点相当于删除有序序列中对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。的一个记录，删除后仍需保持二叉排序树的特性。（对链表进行删除操作是很方便的）（对链表进行删除操作是很方便的）具体算法参看树具体算法参看树D D课件课件讨论讨论2 2：二叉排序树的删除操作：二叉排序树的删除操作14数据结构计算机与信息学院 姜敏 1)1)

14、二叉排序树上查找某关键字等于给定值的结点过二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。程，其实就是走了一条从根到该结点的路径。比较的关键字次数比较的关键字次数此结点的层次数此结点的层次数;最多的比较次数最多的比较次数树的深度（或高度），即树的深度（或高度），即 loglog2 2 n n+1+12)2)一棵二叉排序树的平均查找长度为：一棵二叉排序树的平均查找长度为：3.3.二叉排序树的查找分析二叉排序树的查找分析其中：其中：n ni i 是每层结点个数；是每层结点个数；c ci i 是结点所在层次数；是结点所在层次数；m m 为树深。为树深。15数据结构计

15、算机与信息学院 姜敏 最坏情况：最坏情况：即插入的即插入的n个元素从一开始就有序，个元素从一开始就有序，变成单支树的形态！变成单支树的形态！此时树的深度为此时树的深度为n ;ASL=(n+1)/2 此时查找效率与顺序查找情况相同。此时查找效率与顺序查找情况相同。最好情况最好情况：即：与折半查找中的判定树相同（形态比较均衡）：即：与折半查找中的判定树相同（形态比较均衡）树的深度为：树的深度为：log 2n +1；ASL=(n+1)/n*log 2(n+1)1；与折半查找相同。；与折半查找相同。16数据结构计算机与信息学院 姜敏 3）对有）对有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉

16、排序树的平均查找长度:设每种树态出现概率相设每种树态出现概率相 同同，查找每个关键字也，查找每个关键字也是等概率的。是等概率的。则则ASL求解过程可推导。求解过程可推导。结论：二叉排序树的结论：二叉排序树的ASL2（11/n）ln n问：如何能让二叉排序树的查找过程保持最好情况？问：如何能让二叉排序树的查找过程保持最好情况？17数据结构计算机与信息学院 姜敏 二 平衡二叉树(AVL树）什么是平衡二叉树什么是平衡二叉树(Balanced Binary TreeBalanced Binary Tree)?平衡二叉树是空树平衡二叉树是空树,或者是具有以下性质的二叉树或者是具有以下性质的二叉树:它的左

17、子树和右子树也都是它的左子树和右子树也都是平衡二叉树并且平衡二叉树并且左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过1 1结点的结点的平衡因子平衡因子BFBF (Balance Factor)(Balance Factor)是是左子树的深度减去右子树的深度左子树的深度减去右子树的深度,它只可能是它只可能是-1,0,1-1,0,1平衡二叉树平衡二叉树(也称也称AVLAVL树树)的深度为的深度为O(logO(log2 2N)N)(其中其中N N为结点个数为结点个数)它的平均查找长度也是它的平均查找长度也是O(logO(log2 2N)N)18数据结构计算机与信息学院

18、姜敏 平衡二叉树及平衡因子举例-1100-110平衡的二叉树平衡的二叉树110019数据结构计算机与信息学院 姜敏 不平衡的二叉树不平衡的二叉树-1000-210 2 2-101 00不平衡二叉树及平衡因子举例危急危急结点结点危急危急结点结点20数据结构计算机与信息学院 姜敏 二叉排序树在结点添加过程中失衡二叉排序树在结点添加过程中失衡的几种情况的几种情况LLRRLRRL2a1b0c0c0c0c-1b-1b1b-2a2a-2a21数据结构计算机与信息学院 姜敏 二叉排序树转成平衡树失去平衡后需要进行调整的四种情况(1)单向右旋平衡处理LL当在左子树上插入左结点,使平衡因子由1增至2时(2)单向

19、左旋平衡处理RR当在右子树上插入右结点,使平衡因子由-1增至-2时(3)双向旋转(先左后右)平衡处理LR当在左子树上插入右结点,使平衡因子由1增至2时(4)双向旋转(先右后左)平衡处理RL当在右子树上插入左结点,使平衡因子由-1增至-2时22数据结构计算机与信息学院 姜敏 2A1B0A0BBLBRARhh-1h-1ARBRLLBL 1、LL型平衡旋转型平衡旋转 A的的左子树的左子树左子树的左子树上插入结点，作顺时针旋转。上插入结点，作顺时针旋转。23数据结构计算机与信息学院 姜敏 2、RR型：型：A的的右子树右子树的的右子树右子树上插入结点，作逆时针旋转。上插入结点，作逆时针旋转。-2A-1B

20、0A0BBRBLALh-1BLALRRBRh-1h24数据结构计算机与信息学院 姜敏 2A-1B-1A0CCLBLARh-2h-1h-1LR1Ch-1CR0BBLARCLCR3、LR型：型：A的的左子树左子树的的右子树右子树上插入结点，作两次（逆、顺）旋转。上插入结点，作两次（逆、顺）旋转。25数据结构计算机与信息学院 姜敏 4 RL型：型：在在A的右子树的左子树上插入结点，作两次（顺、逆）旋转。的右子树的左子树上插入结点，作两次（顺、逆）旋转。h-1-2A1B-1B0CCLALh-2h-1RL1Ch-1CR0AALBRCLCRBR26数据结构计算机与信息学院 姜敏 二叉排序树在结点添加平衡化

21、方法总结27数据结构计算机与信息学院 姜敏 二叉排序树转成平衡树示例二叉排序树转成平衡树示例设关键字序列为设关键字序列为(13,24,37,90,53)(13,24,37,90,53)013-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)241337539028数据结构计算机与信息学院 姜敏 练习：下列情况属于哪种失衡状况？应该操作哪些结点？练习：下列情况属于哪种失衡状况？应该操作哪些结点？LR 12,7,9RR 12,192

22、12-1701919080629数据结构计算机与信息学院 姜敏 二叉排序树在结点添加平衡化实例二叉排序树在结点添加平衡化实例例：给定平衡二叉排序树的输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，61122150730数据结构计算机与信息学院 姜敏 例：给定平衡二叉排序树的输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，631数据结构计算机与信息学院 姜敏 例：给定平衡二叉排序树的

23、输入结点序列，请例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。图示结点插入过程树结构的变化。15，12，7，19，24，9，8，5，632数据结构计算机与信息学院 姜敏 失衡二叉排序树平衡化过程特性失衡二叉排序树平衡化过程特性h-1-2A1B-1B0CCLALh-2h-1RL1Ch-1CR0AALBRCLCRBR 1、树的高度不会增加；树的高度不会增加；h1 2、保持了二叉排序树的基本性质。保持了二叉排序树的基本性质。3、使二叉排序查找性能趋近二分查找。使二叉排序查找性能趋近二分查找。33数据结构计算机与信息学院 姜敏 在平衡在平衡树上上进行行查找的找的过程和二叉排序程

24、和二叉排序树相同，因相同，因此此在在查找找过程中和程中和给定定值进行比行比较的关的关键码个数不超个数不超过树的深度。的深度。为了确定含有了确定含有n n个关个关键码的平衡的平衡树的最大深的最大深度，先分析深度度，先分析深度为h h的平衡的平衡树所具有的最少所具有的最少结点数点数。平衡二叉平衡二叉树查找性能分析找性能分析(查找插入平衡化）查找插入平衡化）斐波那契序列斐波那契序列：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,

25、F6 6=8,F=8,F7 7=13,F=13,F8 8212134数据结构计算机与信息学院 姜敏 假假设以以N Nh h表示深度表示深度为h h的平衡的平衡树中含有的最少中含有的最少结点数。点数。显然，然，N N0 0=0=0，N N1 1=1=1，N N2 2=2=2，并且并且N Nh h=N=Nh-1h-1+N+Nh-2h-2+1+1。这个关系和斐波那契序列极个关系和斐波那契序列极为相似。利用相似。利用归纳法法容易容易证明：当明：当h0.h0.因此，在平衡二叉因此，在平衡二叉树上上进行行查找的找的时间复复杂度度为O(logO(log2 2n)n)。问：问：深度深度为6 6的平衡的平衡树最

26、少具有最少具有多少多少结点点？2035数据结构计算机与信息学院 姜敏 平衡树以二叉链表作为存储结构平衡树以二叉链表作为存储结构,每个结点还要每个结点还要增加增加一个平衡因子域一个平衡因子域。平衡树的平衡树的查找运算与普通树型查找完全相同查找运算与普通树型查找完全相同，由于平，由于平衡树附加了平衡条件，其高度与结点数相同的完全树衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。属于同一数量级，所以有较快的查找速度。在插入新结点时，当确定了新结点应插入的位置后，在插入新结点时，当确定了新结点应插入的位置后，需向上寻找有关平衡因子变为需向上寻找有关平衡因子变为+2+

27、2或或-2-2的祖先的祖先，如有这，如有这种结点，则取种结点，则取其中层数居最低者其中层数居最低者，根据不同的情况进，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修每次插入结点后，还需对有关祖先的平衡因子加以修改改。平衡二叉排序树编程实现注意事项平衡二叉排序树编程实现注意事项36数据结构计算机与信息学院 姜敏 v B-树的形态和本质树的形态和本质三 B、B+树111351118127199645334778432139FFFFFFFFFFFF本质：本质：多路查找树多路查找树，查找过程

28、类似于二叉排序树，查找过程类似于二叉排序树非终端结点非终端结点中包含下列信息数据（中包含下列信息数据（n，A0，K1，A1，K2，A2，Kn，An）37数据结构计算机与信息学院 姜敏 v B-树的定义树的定义或曰性质或曰性质 一棵一棵m阶的阶的B-树树，或为空树，或为满足下列特性的，或为空树，或为满足下列特性的m叉树：叉树：1、树中每个结点树中每个结点至多至多有有m棵子棵子树；树；2、若根结点若根结点不是叶子结点，则不是叶子结点，则至少至少有两棵子树；有两棵子树；3、除根之外的除根之外的所有非终端结点至少有所有非终端结点至少有 m/2 棵子树；棵子树；4、所有的非终端结点所有的非终端结点中包含

29、下列信息数据（中包含下列信息数据（n，A0，K1，A1，K2，A2，Kn，An），其中），其中Ki为关键字，为关键字，关键字关键字个数个数n 必须满足必须满足 m/2 1=n=m-1。5、所有的叶子结点都出现在同一层次上，并且不带信息。所有的叶子结点都出现在同一层次上，并且不带信息。38数据结构计算机与信息学院 姜敏 例：一棵四阶的例：一棵四阶的B-树。树。111351118127199645334778432139FFFFFFFFFFFF11bt3543,7818 2739 99 47,53,6439数据结构计算机与信息学院 姜敏 B-树的插入（要求保持树的插入（要求保持B-树性质不变）树性

30、质不变）B-树的生成也是从空树起，逐个插入关键字而得。但由于树的生成也是从空树起，逐个插入关键字而得。但由于B-树结点中得关键字个数必须树结点中得关键字个数必须m/2-1，因此，每次插入一个关键，因此，每次插入一个关键字不是在树中添加一个叶子接点，而是首先在最低层的某个非终字不是在树中添加一个叶子接点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数端结点中添加一个关键字，若该结点的关键字个数不超过不超过m-1，则插入完成，否则要产生结点的则插入完成，否则要产生结点的分裂分裂。例：例：在下面是一棵在下面是一棵3 3阶的阶的B B-树，从中插入元素树，从中插入元素3030，

31、2626，8585。3 12bt4553 9024 3750 100 61 70 40数据结构计算机与信息学院 姜敏 3 12bt4553 9024 30 3750 100 61 70 插入元素插入元素30 3 12bt45 53 9024 26 30 3750 100 61 70 插入元素插入元素2641数据结构计算机与信息学院 姜敏 3 12bt45 53 9024 30 3750 100 61 70 插入元素插入元素26263 12bt4553 9024 30 3750 100 61 70 85 插入元素插入元素85 2642数据结构计算机与信息学院 姜敏 插入元素插入元素85bt45

32、703 12905324 30372650 100 85 61 3 12bt4553 70 9024 3750 100 85 61问：此时插入关键字问：此时插入关键字7 7，如何改变树结构？动手练习一下！，如何改变树结构？动手练习一下！43数据结构计算机与信息学院 姜敏 B-树的删除树的删除 若在若在B-树中删除一个关键字，则首先应找到该关键字所在树中删除一个关键字，则首先应找到该关键字所在结点，并丛中删除之。结点，并丛中删除之。若该结点为若该结点为最下层的非终端结点最下层的非终端结点，且其中的关键字数目不，且其中的关键字数目不小于小于 m/2，则删除完成，否则进行，则删除完成，否则进行“合并

33、合并”结点的操作。结点的操作。3 12bt45 53 9024 30 3750 100 61 70 26直接删除元素直接删除元素6144数据结构计算机与信息学院 姜敏 假若所删除关键字为非终端结点中的假若所删除关键字为非终端结点中的Ki，则可以指针则可以指针Ai所指子树中的最所指子树中的最小关键字小关键字Y替代替代Ki，然后在相应的结点中删除，然后在相应的结点中删除Y。删除元素删除元素243 12bt45 53 9024 30 3750 100 61 70 263 12bt45 53 9026 30 3750 100 61 70 26删除终端结点删除终端结点45数据结构计算机与信息学院 姜敏

34、因此，下面我们可以只需讨论因此，下面我们可以只需讨论删除最下层非终端结点中的关键字删除最下层非终端结点中的关键字的情形的情形。有下面三种可能：。有下面三种可能：1、被删除关键字所在结点中的关键字数目、被删除关键字所在结点中的关键字数目不小于不小于 m/2，则只，则只需从该结点中删去该关键字需从该结点中删去该关键字Ki和相应指针和相应指针Ai，树的其它部分不变。，树的其它部分不变。2、被删除关键字所在结点的关键字数目、被删除关键字所在结点的关键字数目等于等于 m/2-1，而与该，而与该结点相邻的结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于右兄弟（或左兄弟）结点中的关键字数目大于 m/2-1

35、，则只需将其右兄弟结点中的最小（或左兄弟结点中的最大）的则只需将其右兄弟结点中的最小（或左兄弟结点中的最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。靠该上移关键字的关键字下移至被删除关键字所在结点中。46数据结构计算机与信息学院 姜敏 3 12bt45 53 9024 30 3750 100 61 70 26删除终端结点删除终端结点503 12bt45 61 9024 30 3753 100 70 2647数据结构计算机与信息学院 姜敏 3、被删关键字所在结点和其相邻的

36、兄弟结点中的关键字数目均等于、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于 m/2-1。若该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针。若该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字结点中的关键字Ki一起，合并到一起，合并到Ai所指兄弟结点中（若没有右兄弟，则合并所指兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。到左兄弟结点中）。12bt45 53 9025 30 3750 100 61 70 26删除终端结点删除

37、终端结点2612bt45 53 9025 30 3750 100 61 70 48数据结构计算机与信息学院 姜敏 v B+树的定义树的定义 B+树是文件系统所需而出的一种树是文件系统所需而出的一种B-树的变型树。一棵树的变型树。一棵m阶的阶的B+树和树和m阶的阶的B-树的区别在于：树的区别在于：1、有、有n棵子树的结点汇总含有棵子树的结点汇总含有n个关键字。个关键字。2、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键、所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小而大顺序链接。字记录的指针，且叶子结点本身依关键字的大小而大顺序链接。3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根、所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。结点）中的最大（或最小）关键字。在在B+树上进行随机查找、插入和删除的过程与树上进行随机查找、插入和删除的过程与B-树基本类似，在此不树基本类似，在此不做详细的介绍。做详细的介绍。49数据结构计算机与信息学院 姜敏 此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢