代码编织梦想

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树的定义为止。

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Rukia0213/article/details/130801381