408考研之数据结构的查找——b树-爱代码爱编程
TIPS:考研中的难点与重点,侧重于考查B树的性质,插入,查找与删除。而对于B树的代码,一般情况下不要求掌握。
我们主要关注的是B树的性质和B树的手算方法。(插入删除操作)
两个概念:
终端结点:下面的含有实际数据的结点,称为终端节点。
叶子结点:最下面的这些失败结点,称为叶子结点。
B树,又称为多路平衡查找树(基于二叉查找树)。
B树中所有结点的孩子个数最大值,称为B树的阶,通常用M表示。
一颗M阶B树,要么是一棵空树,要么为满足如下特性的M叉树:
1,树中每个结点,至多有M棵子树(即M个分支)==至多含有M-1个关键字。
2,若根结点不是终端结点,则至少有两颗子树。
3,除了根结点外的所有非叶结点至少有(向上取整)棵子树,即至少含有。
4,所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点,或者是类似于折半查找判定树的失败结点,实际上这些结点不存在,指向这些结点的指针为空)。
B树的核心特性:
TIPS:大部分学校算B树的高度,都不包括叶子结点,也就是失败结点。
TIPS:首先在求这个问题之前,需要搞清楚一个老生常谈的核心二叉树考点:具有N个结点的完全二叉树的高度为:_________???
高度为h的满二叉树,共有2^h -1个结点;那么此时结点个数N和高度h的关系为:
则h>=log2 (n+1);又因为h高度为整数,所以高度h可以表示为:(向上取整)。
★★★问题:含N个关键字的M阶B树,最小高度,最大高度为多少?
TIPS:大部分学校算B树的高度,都不包括叶子结点,也就是失败结点。
最小高度————让每个结点尽可能填满树,以M阶B树为例,有M-1个关键字,也就是M个分叉(M棵子树),则有:
第一层是M-1个关键字,第二层有M*(M-1)个关键字,第三层有M*(M-1)*M个关键字,所以第h层有M*(M-1)*M*M......共h-1个M相乘,那么有:(M-1)(1+M+M^2+M^3+...+M^h-1)=。
最大高度————让各层的分叉尽可能的少,即根结点只有两个分叉,其他结点只有(向上取整)个分叉。
我们可以从h层高的树的叶子结点入手,计算叶子结点的个数(N+1)与最少情况下每层结点的个数进行对比即可,具体方法如下:
☆各层的结点至少有:第一层1个,第二层2个,第三层2个,第h层2*()^(h-2),那么h+1层共有叶子结点2*()^(h-1)个。
N个关键字的B树必然有N+1个叶子结点(可以理解为二叉排序树查找失败的那些失败结点,失败结点实际上指向NULL为空,但是个数为结点个数+1),王道书上解释:N个关键字将数域切分为N+1个区间;。
★★★综上,N个关键字的M阶B树,最小和最大高度为:。
该知识点很陌生,需要强行多次记忆,成功的秘诀在于:反复,多次和重复。
接下来重点关注的内容是B树的插入删除操作,以5阶B树作为插入删除案例进行演示。
B树插入情景分析:
1,在插入了一个KEY=80的数据后,导致了原结点的关键字超过了上限,则从中间位置将关键字分为两部分,左边部分包含的关键字放在原结点中,右边部分包含的关键字放到新结点中,中间位置的结点插入原结点的父结点,如图所示:
2,新插入的元素一定是插入到最底层的“终端结点”,用查找来确定插入的位置。
在插入KEY=88后,导致原结点关键字数超过上限,则从中间位置将其中的关键字分为两部分,左部分包含的关键字放在原结点中,右部分包含的关键字放到新结点中,中间位置的结点插入到原结点的父亲节点中,跟情况1差不多,如图所示:
3,在插入KEY=73后,导致原结点关键字数超过上限,则从中间位置将其中的关键字分为两部分,左部分包含的关键字放在原结点中,右部分包含的关键字放到新结点中,中间位置的结点插入到原结点的父亲节点中,跟情况1和2差不多,如图所示:
若此时导致其父结点的关键字个数也超过了上限,则继续进行这种分裂操作,直至这个过程传到根结点为止,进而导致B树高度增加1,如图所示:
B树删除情景分析:
1,若被删除关键字在终端结点,则直接删除该关键字(要注意结点关键字的个数是否低于下限, 我们当前以被删除的KEY=60为例,如图所示:
2,重点:若被删除的关键字在非终端结点,则用直接前驱或直接后继来替代被删除的关键字。
对非终端结点关键字的删除,必然可以转化为对终端结点的删除操作。
直接前驱:当前关键字左侧指针所指子树中“最右下”的元素。
直接后继:当前关键字右侧指针所指子树中“最左下”的元素。
我们当前以被删除的KEY=80为例,如图所示:
直接前驱:
直接后继:
3,兄弟够借用。若被删除的关键字所在结点删除前的关键字个数低于下限,且与此结点左(或者右)兄弟结点的关键字个数还很宽裕,则需要调整该结点左(或者右)兄弟结点及其双亲结点,当前以删除KEY=38为案例进行演示,如图所示:
当右兄弟很宽裕时,用当前结点的后继结点以及后继的后继来填补空缺。
同理可得:当左兄弟很宽裕时,用当前结点的前驱结点以及前驱的前驱来填补空缺。
4,兄弟不够借。若该结点被删除,导致删除后的结点关键字个数低于下限,且此时与该结点相邻的左右兄弟结点的关键字个数均为最低值,则将关键字删后,与左(或者右)兄弟结点及其双亲结点的对应关键字进行合并。以删除KEY=49为案例进行演示,如图所示:
此时左右兄弟个数已经足够B树要求,然而父结点因为借位,导致不满足B树的要求,如图所示:
在合并过程中,双亲结点的关键字个数会减1.若双亲结点是根结点且关键字个数已为0,则直接将根结点删除并将合并后的新结点作为根结点。
若双亲结点不是根结点,且关键字个数小于,则又要与它自己的兄弟结点进行调整或者合并操作,并重复上述步骤,直到满足B树的定义为止。