B+ tree 删除算法

MD
B+ 树有两种定义，一是严蔚敏老师的数据结构一书的定义，二是维基百科的定义，本文采用维基百科的定义并实现。

https://en.wikipedia.org/wiki/B%2B_tree
前提知识：掌握B-tree ,了解B+插入算法及流程。

1.算法描述

与B-tree不同，B+tree只能从叶子删除，从叶子删除元素分为三次循环的三种情形：

• 第一次循环，如果满足条件结束，否则：
• 第二次循环，如果满足条件结束，否则：
• 第三次循环，如满足条件线束，否则继续调用第三次循环。

第一次循环的三种情形：


     情形1：
若x->keynum>Min，则只需删去K及其右指针(*x是叶子)即可使，父节点的索引元素也要重新调整，
     如果K还出现在非父索引节点中，取K的后继元素代替之，删除操作结束。


    情形2：
若x->keynum=Min，如左或右兄弟Keynum>Min,借一个填充K，如果K同时作为非父节点的索引元素，用新的K位置上的值并取代其索引元素；
        如果因此父节点的索引被打乱，则索引元素重新取该元素对应的孩子的最小元素。如果该节点是索引节点，孩子一同过继。
     情形3：
若x->keynum=Min，  第一步：左或右合并，删除本元素，
     剩下的元素和孩子过继给左或右兄弟，删除节点，叶子链接调整。

     第二步：进行第2次递归调用干掉父元素。递归调用步骤：
              删除本元素，剩下的元素和孩子过继给左兄弟

第二次循环的三种情形：

   情形一：只需删去K，移位，调整索引，但不需要用后继元素做替换
   情形二：如左或右兄弟Keynum>Min,借一个填充K，如果K同时作为非父节点的索引元素，取后继元素取代之，
   父节点相应元素的顺序可能被打破，需要取该位置后继元素取代之。删除结束。
   情形三：
     左合并：删除本元素，剩下的元素和孩子过继给左兄弟。如果它的孩子是叶子，
     调整索引（哪个索引有变动重排哪个，不必全部重排）递归调用删除父元素。
     右合并；与左合并一样.

第三次循环的三种情形：

    与B-树步骤一样，省略。

2. 举例子

插入：
char r[21] = {‘C’, ‘N’, ‘G’, ‘A’, ‘H’, ‘E’, ‘K’, ‘Q’, ‘M’, ‘F’, ‘W’, ‘L’, ‘T’, ‘Z’, ‘D’, ‘P’, ‘R’, ‘X’, ‘Y’, ‘S’,’B’};

Min= (max_degree+1)/2-1;
Max=max_degree-1;
约定：
本例m=5阶。
S3=situation 3=情形3
S2=situation 2=情形2
S1=situation 1=情形1
S2-right = 情形2,向右兄弟借一个元素
S2-left = 情形2,向左兄弟借一个元素
S3-right -> S2-right ，S3 第一次右合并，第二次情形2的右兄弟借元素
S1 delete A :

delete : A
第 1 层， 1 node : K 
   第 2 层， 2 node : D G 
      第 3 层， 2 node : B C 
      第 3 层， 3 node : D E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 

S2-right delete AB

delete : A
第 1 层， 1 node : K 
   第 2 层， 2 node : D G 
      第 3 层， 2 node : B C 
      第 3 层， 3 node : D E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 
delete : B
第 1 层， 1 node : K 
   第 2 层， 2 node : E G 
      第 3 层， 2 node : C D 
      第 3 层， 2 node : E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 

S2-left delete DE

delete : D
第 1 层， 1 node : K 
   第 2 层， 2 node : E G 
      第 3 层， 3 node : A B C 
      第 3 层， 2 node : E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 
delete : E
第 1 层， 1 node : K 
   第 2 层， 2 node : C G 
      第 3 层， 2 node : A B 
      第 3 层， 2 node : C F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 

S3-right -> S2-right delete ABC:

delete : A
第 1 层， 1 node : K 
   第 2 层， 2 node : D G 
      第 3 层， 2 node : B C 
      第 3 层， 3 node : D E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 
delete : B
第 1 层， 1 node : K 
   第 2 层， 2 node : E G 
      第 3 层， 2 node : C D 
      第 3 层， 2 node : E F 
      第 3 层， 2 node : G H 
   第 2 层， 4 node : N Q T X 
      第 3 层， 3 node : K L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 
delete : C
第 1 层， 1 node : N 
   第 2 层， 2 node : G K 
      第 3 层， 3 node : D E F 
      第 3 层， 2 node : G H 
      第 3 层， 3 node : K L M 
   第 2 层， 3 node : Q T X 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R S 
      第 3 层， 2 node : T W 
      第 3 层， 3 node : X Y Z 

为了测试其它情形，重新插入：
char r[17] = {‘C’, ‘G’, ‘L’, ‘N’,’Q’, ‘M’, ‘T’, ‘D’, ‘P’, ‘R’,’H’,’J’,K,’I’,’F’,’A’,’B’};

S3-left -> S2-left delete RT

delete : R
第 1 层， 1 node : L 
   第 2 层， 3 node : C G I 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 2 node : G H 
      第 3 层， 3 node : I J K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 2 node : Q T 
delete : T
第 1 层， 1 node : I 
   第 2 层， 2 node : C G 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 2 node : G H 
   第 2 层， 2 node : L N 
      第 3 层， 3 node : I J K 
      第 3 层， 2 node : L M 
      第 3 层， 3 node : N P Q 

S3-left -> S3-right delete IJAB

delete : I
第 1 层， 1 node : L 
   第 2 层， 3 node : C G J 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 2 node : G H 
      第 3 层， 2 node : J K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R T 
delete : J
第 1 层， 1 node : L 
   第 2 层， 2 node : C G 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 3 node : G H K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R T 
delete : A
第 1 层， 1 node : L 
   第 2 层， 2 node : D G 
      第 3 层， 2 node : B C 
      第 3 层， 2 node : D F 
      第 3 层， 3 node : G H K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R T 
delete : B
第 1 层， 4 node : G L N Q 
   第 2 层， 3 node : C D F 
   第 2 层， 3 node : G H K 
   第 2 层， 2 node : L M 
   第 2 层， 2 node : N P 
   第 2 层， 3 node : Q R T 

S3-right -> S3-left delete IJL

delete : I
第 1 层， 1 node : L 
   第 2 层， 3 node : C G J 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 2 node : G H 
      第 3 层， 2 node : J K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R T 
delete : J
第 1 层， 1 node : L 
   第 2 层， 2 node : C G 
      第 3 层， 2 node : A B 
      第 3 层， 3 node : C D F 
      第 3 层， 3 node : G H K 
   第 2 层， 2 node : N Q 
      第 3 层， 2 node : L M 
      第 3 层， 2 node : N P 
      第 3 层， 3 node : Q R T 
delete : L
第 1 层， 4 node : C G M Q 
   第 2 层， 2 node : A B 
   第 2 层， 3 node : C D F 
   第 2 层， 3 node : G H K 
   第 2 层， 3 node : M N P 
   第 2 层， 3 node : Q R T 

后续上传源码