B树的插入、删除操作

时间:2022-12-20 09:53:28

B树的插入、删除操作

 

     上面第2小节学习简单介绍了利用B树这种结构如何访问外存磁盘中的数据的情况,下面咱们通过另外一个实例来对这棵B树的插入(insert,删除(delete)基本操作进行详细的介绍。

 

    但在此之前,咱们还得简单回顾下一棵m阶的 (m叉树)的特性,如下:

 

1.    树中每个结点含有最多含有m个孩子,即m满足:ceil(m/2)<=m<=m

 

2.    除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);

 

3.    若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);

 

4.    所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为null)

 

5.    每个非终端结点中包含有n个关键字信息: (nP0K1P1K2P2......KnPn)。其中:

 


      a)   Ki (i=1...n)

 

为关键字,且关键字按顺序升序排序K(i-1)< Ki

 

 

 
       b)   Pi
为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1) 

 


       c)  

 

除根结点之外的结点的关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1(叶子结点也必须满足此条关于关键字数的性质,根结点除外)。

 

 

 

      那好!下面咱们以一棵5阶(即树中任一结点至多含有4个关键字,5棵子树)B树实例进行讲解(如下图所示)

备注:

1.    关键字数(2-4个)针对--非根结点(包括叶子结点在内),孩子数(3-5个)--针对根结点和叶子结点之外的内结点。当然,根结点是必须至少有2个孩子的,不然就成直线型搜索树了。

2.    曾在一次面试中被问到,一棵含有N个总关键字数的m阶的B树的最大高度是多少?答曰:log_ceilm/2(上面中关于mB树的第1点特性已经提到:树中每个结点含有最多含有m个孩子,即m满足:ceil(m/2)<=m<=m。而树中每个结点含孩子数越少,树的高度则越大,故如此)。在2012微软4月份的笔试中也问到了此问题。更多原理请看上文第3小节末:B树的高度。

下图中关键字为大写字母,顺序为字母升序。

结点定义如下:

typedef struct{ int Count; // 当前节点中关键元素数目 ItemType Key[4]; // 存储关键字元素的数组 long Branch[5]; // 伪指针数组,(记录数目)方便判断合并和分裂的情况 } NodeType;

 

 

如图:


B树的插入、删除操作
 

 

插入(insert)操作

    插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素,注意:如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行分裂,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要分裂操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。如下图所示:
B树的插入、删除操作


    1OK,下面咱们通过一个实例来逐步讲解下。插入以下字符字母到一棵空的树中(非根结点关键字数小了(小于2个)就合并,大了(超过4个)就分裂):C N G A H E K Q M F W L T Z D P R X Y S,首先,结点空间足够,4个字母插入相同的结点中,如下图:


B树的插入、删除操作

 

       2、当咱们试着插入H时,结点发现空间不够,以致将其分裂成2个结点,移动中间元素G上移到新的根结点中,在实现过程中,咱们把AC留在当前结点中,而HN放置新的其右邻居结点中。如下图:

 

 
B树的插入、删除操作
 

       3、当咱们插入E,K,Q时,不需要任何分裂操作。 如图:

 

 

B树的插入、删除操作
 
 

        4、插入M需要一次分裂,注意M恰好是中间关键字元素,以致向上移到父节点中。如图:

 

 
B树的插入、删除操作
 

        5、插入F,W,L,T不需要任何分裂操作。如图:

 

 
B树的插入、删除操作
 

       6、插入Z时,最右的叶子结点空间满了,需要进行分裂操作,中间元素T上移到父节点中,注意通过上移中间元素,树最终还是保持平衡,分裂结果的结点存在2个关键字元素。如图:


B树的插入、删除操作
 

 

 

       7、插入D时,导致最左边的叶子结点被分裂,D恰好也是中间元素,上移到父节点中,然后字母P,R,X,Y陆续插入不需要任何分裂操作(别忘了,树中至多5个孩子)。如图:


 B树的插入、删除操作

 

       8、最后,当插入S时,含有N,P,Q,R的结点需要分裂,把中间元素Q上移到父节点中,但是情况来了,父节点中空间已经满了,所以也要进行分裂,将父节点中的中间元素M上移到新形成的根结点中,注意以前在父节点中的第三个指针在修改后包括DG节点中。这样具体插入操作的完成,下面介绍删除操作,删除操作相对于插入操作要考虑的情况多点。如图:

B树的插入、删除操作


 

 

 

删除(delete)操作


1)删除操作的两个步骤
   
  第一步骤:在树中查找被删关键字K所在的地点
    
 第二步骤:进行删去K的操作

2)删去K的操作
    
 B-树是二叉排序树的推广,中序遍历B-树同样可得到关键字的有序序列(具体遍历算法【参见练习】)。任一关键字K的中序前趋(后继)必是K的左子树(右子树)中最右()下的结点中最后(最前)一个关键字。


    
 若被删关键字K所在的结点非树叶,则用K的中序前趋(或后继)K'取代K,然后从叶子中删去K'。从叶子*x开始删去某关键字K的三种情形为:


    
 情形一:若x->keynum>Min,则只需删去K及其右指针(*x是叶子,K的右指针为空)即可使删除操作结束。

 

 

 

注意: Min=【M/2】-1


    
 情形二:若x->keynum=Min,该叶子中的关键字个数已是最小值,删K及其右指针后会破坏B-树的性质(3)。若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min,则将*y中的最大(或最小)关键字上移至双亲结点*parent中,而将*parent中相应的关键字下移至x中。显然这种移动使得双亲中关键字数目不变;*y被移出一个关键字,故其keynum1,因它原大于Min,故减少1个关键字后keynum仍大于等于Min;而*x中已移入一个关键字,故删K*x中仍有Min个关键字。涉及移动关键字的三个结点均满足B-树的性质(3) 请读者验证,上述操作后仍满足B-树的性质(1)。移动完成后,删除过程亦结束。


    
 情形三:若*x及其相邻的左右兄弟(也可能只有一个兄弟)中的关键字数目均为最小值Min,则上述的移动操作就不奏效,此时须*x和左或右兄弟合并。不妨设*x有右邻兄弟*y(对左邻兄弟的讨论与此类似),在*x中删去K后,将双亲结点*parent中介于*x*y之间的关键字K,作为中间关键字,与并x*y中的关键字一起"合并"为一个新的结点取代*x*y。因为*x*y原各有Min个关键字,从双亲中移人的K'抵消了从*x中删除的K,故新结点中恰有2Min(2m/2-2≤m-1)个关键字,没有破坏B-树的性质(3)。但由于K'从双亲中移到新结点后,相当于从*parent中删去了K',若parent->keynum原大于Min,则删除操作到此结束;否则,同样要通过移动*parent的左右兄弟中的关键字或将*parent与其 左右兄弟合并的方法来维护B-树性质。最坏情况下,合并操作会向上传播至根,当根中只有一个关键字时,合并操作将会使根结点及其两个孩子合并成一个新的根,从而使整棵树的高度减少一层。如图
    
 
B树的插入、删除操作
 

     
  
分析:
 
    1个被删的关键字h是在叶子中,且该叶子的keynum>Min(5B-树的Min=2),故直接删去即可。第2个删去的r不在叶子中,故用中序后继s取代r,即把s复制到r的位置上,然后从叶子中删去s。第3个删去的p所在的叶子中的关键字数目是最小值Min,但其右兄弟的keynum>Min,故可以通过左移,将双亲中的s移到p所在的结点,而将右兄弟中最小(即最左边)的关键字t上移至双亲取代s。当删去d时,d所在的结点及其左右兄弟均无多余的关键字,故需将删去d后的结点与这两个兄弟中的一个(图中是选择左兄弟(ab))及其双亲中分隔这两个被合并结点的关键字c合并在一起形成一个新结点(abce)。但因为双亲中失去ckeynum<Min,故必须对该结点做调整操作,此时它只有一个右兄弟,且右兄弟无多余的关键字,不可能通过移动关键字来解决。因此引起再次合并,因根只有一个关键字,故合并后树高度减少一层,从而得到上图的最后一个图。