B+树的插入、删除（附源代码）

作者：batman@zhou | 来源：互联网 | 2023-05-17 12:48

B+TreeIndexB+树的插入B+树的删除完整测试代码BasicB+树和B树类似（有关B树：http:www.cnblogs.comYu

B+ Tree

Index

B+树的插入
B+树的删除
完整测试代码

Basic

B+树和B树类似（有关B树：http://www.cnblogs.com/YuNanlong/p/6354029.html，区别主要在于叶节点，如果在父节点的Child数组中指向某一叶节点指针的下标为Index，则该叶节点中的最大数据值与其父节点中Key[Index]的值相等，并且除最右侧的叶节点之外所有叶节点都有一个指针指向其右边的兄弟节点，因此所有非叶节点中数据值都在叶节点中有相同的值与之对应。

下面是一些声明和定义：

typedef int ElementType;
typedef int* PtrElementType;

typedef enum Bool BoolType;
enum Bool{
    False = 0,
    True = 1
};

typedef struct TreeNode *PtrBpNode;
typedef struct TreeNode BpNode;
struct TreeNode{
    int Num;
    BoolType IsLeaf;
    PtrElementType Key;
    PtrBpNode *Child;
    PtrBpNode Next;
};

typedef struct Tree *PtrBp;
struct Tree{
    PtrBpNode Root;
};

void ShiftKey(PtrElementType Key, BoolType Direction, int Begin, int End){
    int i;
    
    if(True == Direction){
        for(i = End; i >= Begin; i--){
            Key[i + 1] = Key[i];
        }
    }
    else{
        for(i = Begin; i <= End; i++){
            Key[i - 1] = Key[i];
        }
    }
}

void ShiftChild(PtrBpNode *Child, BoolType Direction, int Begin, int End){
    int i;
    
    if(True == Direction){
        for(i = End; i >= Begin; i--){
            Child[i + 1] = Child[i];
        }
    }
    else{
        for(i = Begin; i <= End; i++){
            Child[i - 1] = Child[i];
        }
    }
}

int GetIndex(PtrElementType Key, int Size, ElementType Val){
    int i;
    
    for(i = 0; i         if(Key[i] >= Val){
            break;
        }
    }
    
    return i;
}

void BpPrintTree(PtrBpNode Root){
    int i;
    
    if(NULL == Root){
        return;
    }
    
    putchar('[');
    for(i = 0; i Num; i++){
        printf("%d", Root->Key[i]);
        if(i != Root->Num - 1){
            putchar(' ');
        }
    }
    putchar(']');
    printf("%d ", Root->IsLeaf);
    printf("%d", Root->Num);
    putchar('\n');
    
    for(i = 0; i <= Root->Num; i++){
        BpPrintTree(Root->Child[i]);
    }
}

void BpCreateTree(PtrBp T){
    int i;
    int a[] = {12,1,9,2,0,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17,20,21,23};
    
    for(i = 0; i <23; i++){
        BpInsert(T, a[i]);
        BpPrintTree(T->Root);
        printf("The End\n");
    }
}

Insert

B+树的插入只需要在B树插入的基础上处理叶节点的特殊情况。所以差异的部分主要是分裂节点的函数：

void BpSpilitNode(PtrBpNode SpilitNodeP, int ChildIndex){
    int i;
    PtrBpNode NewNode, SubNode = SpilitNodeP->Child[ChildIndex];
    
    if(True == SubNode->IsLeaf){
        NewNode = BpAllocateNode(True);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        NewNode->Num = MinDegree - 1;
        SubNode->Num = MinDegree;
        NewNode->Next = SubNode->Next;
        SubNode->Next = NewNode;
    }
    else{
        NewNode = BpAllocateNode(False);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        for(i = 0; i             NewNode->Child[i] = SubNode->Child[i + MinDegree];
        }
        NewNode->Num = SubNode->Num = MinDegree - 1;
    }
    
    ShiftKey(SpilitNodeP->Key, True, ChildIndex, SpilitNodeP->Num - 1);
    ShiftChild(SpilitNodeP->Child, True, ChildIndex + 1, SpilitNodeP->Num);
    SpilitNodeP->Key[ChildIndex] = SubNode->Key[MinDegree - 1];
    SpilitNodeP->Child[ChildIndex + 1] = NewNode;
    (SpilitNodeP->Num)++;
}

这个函数将叶节点的分裂和非叶节点的分裂作为两种情况来处理，而实际上这个函数还是可以优化的。非叶节点的分裂和B树的一样；叶节点的分裂则是将满叶节点分裂为数据量为Minimum Degree和Minimum Degree - 1的两个节点，同时将大小为Minimum Degree的节点中的最大数据（其实就是原满叶节点的数据中值）向上插入到该叶节点的父节点中，当然还需要将叶节点中指向兄弟节点的指针进行赋值，相当于是单链表中的插入操作。与B树一样，这里也需要注意对于节点结构中IsLeaf成员的赋值。对于满叶节点的分裂，与B树的区别就在于B树是将满叶节点分裂为数据量均为Minimum Degree - 1的两个节点，因此同样是将原满叶节点的数据中值向上插入到其父节点中，B+树在执行完分裂叶节点的操作后，该数据中值仍然保留在分裂后的某一叶节点中，而B树在执行完分裂叶节点的操作后，相当于是把该数据中值从叶节点中删除了。

完整的插入操作：

PtrBpNode BpAllocateNode(BoolType IsLeaf){
    int i;
    PtrBpNode NewNode = (PtrBpNode)malloc(sizeof(BpNode));
    
    NewNode->Num = 0;
    if(True == IsLeaf){
        NewNode->IsLeaf = True;
    }
    else{
        NewNode->IsLeaf = False;
    }
    NewNode->Key = (PtrElementType)malloc(sizeof(ElementType) * (MinDegree * 2 - 1));
    NewNode->Child =(PtrBpNode*)malloc(sizeof(PtrBpNode) * MinDegree * 2);
    for(i = 0; i 2; i++){
        NewNode->Child[i] = NULL;
    }
    NewNode->Next = NULL;
    
    return NewNode;
}

void BpInsert(PtrBp T, ElementType Val){
    PtrBpNode NewNode;
    
    if(MinDegree * 2 - 1 == T->Root->Num){
        NewNode = BpAllocateNode(False);
        NewNode->Child[0] = T->Root;
        T->Root = NewNode;
        BpSpilitNode(NewNode, 0);
    }
    
    BpInsertNonFull(T->Root, Val);
}

void BpInsertNonFull(PtrBpNode CurrentNode, ElementType Val){
    int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);
    
    if(True == CurrentNode->IsLeaf){
        ShiftKey(CurrentNode->Key, True, Index, CurrentNode->Num - 1);
        CurrentNode->Key[Index] = Val;
        (CurrentNode->Num)++;
    }
    else{
        if(MinDegree * 2 - 1 == CurrentNode->Child[Index]->Num){
            BpSpilitNode(CurrentNode, Index);
            //Caution
            if(CurrentNode->Key[Index]                 Index++;
            }
        }
        
        BpInsertNonFull(CurrentNode->Child[Index], Val);
    }
}

void BpSpilitNode(PtrBpNode SpilitNodeP, int ChildIndex){
    int i;
    PtrBpNode NewNode, SubNode = SpilitNodeP->Child[ChildIndex];
    
    if(True == SubNode->IsLeaf){
        NewNode = BpAllocateNode(True);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        NewNode->Num = MinDegree - 1;
        SubNode->Num = MinDegree;
        NewNode->Next = SubNode->Next;
        SubNode->Next = NewNode;
    }
    else{
        NewNode = BpAllocateNode(False);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        for(i = 0; i             NewNode->Child[i] = SubNode->Child[i + MinDegree];
        }
        NewNode->Num = SubNode->Num = MinDegree - 1;
    }
    
    ShiftKey(SpilitNodeP->Key, True, ChildIndex, SpilitNodeP->Num - 1);
    ShiftChild(SpilitNodeP->Child, True, ChildIndex + 1, SpilitNodeP->Num);
    SpilitNodeP->Key[ChildIndex] = SubNode->Key[MinDegree - 1];
    SpilitNodeP->Child[ChildIndex + 1] = NewNode;
    (SpilitNodeP->Num)++;
}

记录自己码代码过程中的一个小bug

当然以上操作中的BpInsertNonFull函数，我自己在第一遍写的时候出过一个小bug，对于以上代码中的Caution注释行处的内层if语句块，我一开始没有将其放在外层的if语句块中，而是放在外层if语句块外面，紧接着外层if语句执行，但是应当注意到此函数中的Index变量有可能等于数组的Size，因此如果内层if语句块放在外面，会使得无论是否执行分裂都要通过Index来访问数组（在if条件判断中），这样就可能出现越界的情况，而现在这样的处理使得只有执行分裂操作后才会通过Index来访问数组，而分裂后数组Size加1，也就不存在越界的问题了。

Delete

B+树的删除虽然有很多情况需要处理，但是其中的一部分都与B树相同，这里只记录不同于B树的情况处理，主要也是为了维护B+树叶节点的特有性质。

待删除数据Val在该节点中，且该节点的子节点是叶节点，记该节点为CurrentNode，待删除数据Val在该节点的Key数组中的下标为Index，并记该节点的Child数组中下标为Index的元素所指向的节点为Precursor，下标为Index + 1的元素所指向的节点为Successor。

如果Precursor中的数据量大于Minimum Degree - 1，用Precursor中第二大的数据值代替CurrentNode中的Val，并在Precursor中递归删除Val。
如果Successor中的数据量大于Minimum Degree - 1，用Successor中的最小数据值代替CurrentNode和Precursor中的Val值，并在Successor中递归删除Val。
如果以上均不满足，则合并Precursor和Successor，然后在合并后的新节点中递归删除Val。

待删除数据Val不在该节点中，且该节点的子节点是叶节点，记该节点为CurrentNode，待删除数据Val在该节点的Key数组中的下标为Index，并记该节点的Child数组中下标为Index的元素所指向的节点为SubNode，下标为Index - 1的元素所指向的节点为Precursor（如果存在），下标为Index + 1的元素所指向的节点为Successor（如果存在）。

如果SubNode中的数据量大于Minimum Degree - 1，则直接在SubNode中递归删除即可。
如果SubNode中的数据量小于或等于Minimum Degree - 1：
- 如果Precursor中的数据量大于Minimum Degree - 1，则将CurrentNode中下标为Index - 1的数据值插入SubNode中，并将SubNode中记录数据量的成员Num加1，用Precursor中的第二大数据值填入CurrentNode中下标为Index - 1的空缺，并将Precursor中记录数据量的成员Num减1，最后在SubNode中递归删除Val。
- 如果Successor中的数据量大于Minimum Degree - 1，则将Successor中的最小数据插入SubNode中，并将SubNode中记录数据量的成员Num加1，同时CurrentNode的Key数组中下标为Index的元素值也由Successor中的最小数据代替，并将Successor中Key数组的部分元素向左移动一位，相应的Successor中记录数据量的成员Num也应减1，最后在SubNode中递归删除Val。
- 如果以上均不符合，则将SubNode与Precursor或Successor合并（两者不一定均存在，选择存在的进行合并），然后在合并后的节点中递归删除Val。

当然删除节点操作中的部分情况涉及移动数组的部分元素，尤其是对于内点，要注意除了Key数组，还要移动Child数组。

当然因为叶节点的特殊性质，合并操作也有所不同，区别就在于合并叶节点时，合并后节点的大小为Minimum Degree * 2 - 2，因为两被合并叶节点在其父节点中所夹元素同样存在于叶节点中，所以在合并中也就不需要将这个值重复插入合并节点中了。

完整的删除操作：

void BpDelete(PtrBp T, PtrBpNode CurrentNode, ElementType Val){
    int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);
    PtrBpNode Precursor, SubNode, Successor;
    
    if(Index Num && Val == CurrentNode->Key[Index]){
        
        if(True == CurrentNode->IsLeaf){
            ShiftKey(CurrentNode->Key, False, Index + 1, CurrentNode->Num - 1);
            (CurrentNode->Num)--;
            return;
        }
        else{
            Precursor = CurrentNode->Child[Index];
            Successor = CurrentNode->Child[Index + 1];
            
            if(Precursor->Num >= MinDegree){
                if(True == SubNode->IsLeaf){
                    CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 2];
                }
                else{
                    CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 1];
                }
                
                BpDelete(T, Precursor, Precursor->Key[SubNode->Num - 1]);
            }
            else if(Successor->Num >= MinDegree){
                CurrentNode->Key[Index] = Successor->Key[0];
                if(True == SubNode->IsLeaf){
                    SubNode->Key[SubNode->Num - 1] = CurrentNode->Key[Index];
                }
                
                BpDelete(T, Successor, Successor->Key[0]);
            }
            else{
                BpMerge(T, CurrentNode, Index, Index + 1);
                
                BpDelete(T, Precursor, Val);
            }
        }
        
    }
    else{
        
        if(True == CurrentNode->IsLeaf){
            return;
        }
        else{
            if(Index > 0){
                Precursor = CurrentNode->Child[Index - 1];
            }
            SubNode = CurrentNode->Child[Index];
            if(Index Num){
                Successor = CurrentNode->Child[Index + 1];
            }
            
            
            if(SubNode->Num >= MinDegree){
                BpDelete(T, SubNode, Val);
            }
            else{
                if(Index > 0 && Precursor->Num >= MinDegree){
                    ShiftKey(SubNode->Key, True, 0, SubNode->Num - 1);
                    SubNode->Key[0] = CurrentNode->Key[Index - 1];
                    
                    if(True == SubNode->IsLeaf){
                        CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 2];
                    }
                    else{
                        CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 1];
                        ShiftChild(SubNode->Child, True, 0, SubNode->Num);
                        SubNode->Child[0] = Precursor->Child[Precursor->Num];
                    }
                    (SubNode->Num)++;
                    (Precursor->Num)--;
                    
                    BpDelete(T, SubNode, Val);
                }
                else if(Index Num && Successor->Num >= MinDegree){
                    if(True == SubNode->IsLeaf){
                        SubNode->Key[SubNode->Num] = Successor->Key[0];
                    }
                    else{
                        SubNode->Key[SubNode->Num] = CurrentNode->Key[Index];
                    }
                    CurrentNode->Key[Index] = Successor->Key[0];
                    SubNode->Child[SubNode->Num + 1] = Successor->Child[0];
                    (SubNode->Num)++;
                    
                    ShiftKey(Successor->Key, False, 1, Successor->Num - 1);
                    ShiftChild(Successor->Child, False, 1, Successor->Num);
                    (Successor->Num)--;
                    
                    BpDelete(T, SubNode, Val);
                }
                else{
                    if(Index > 0){
                        BpMerge(T, CurrentNode, Index - 1, Index);
                        BpDelete(T, Precursor, Val);
                    }
                    else{
                        BpMerge(T, CurrentNode, Index, Index + 1);
                        BpDelete(T, SubNode, Val);
                    }
                }
            }
        }
        
    }
}

void BpMerge(PtrBp T, PtrBpNode CurrentNode, int LeftIndex, int RightIndex){
    int i;
    PtrBpNode LeftNode = CurrentNode->Child[LeftIndex];
    PtrBpNode RightNode = CurrentNode->Child[RightIndex];
    
    if(True == LeftNode->IsLeaf){
        for(i = 0; i 1; i++){
            LeftNode->Key[i + MinDegree - 1] = RightNode->Key[i];
        }
        LeftNode->Num = MinDegree * 2 - 2;
        LeftNode->Next = RightNode->Next;
    }
    else{
        for(i = 0; i 1; i++){
            LeftNode->Key[i + MinDegree] = RightNode->Key[i];
        }
        for(i = 0; i             LeftNode->Key[i + MinDegree] = RightNode->Key[i];
        }
        LeftNode->Key[MinDegree - 1] = CurrentNode->Key[LeftIndex];
        LeftNode->Num = MinDegree * 2 - 1;
    }
    
    ShiftKey(CurrentNode->Key, False, LeftIndex + 1, CurrentNode->Num - 1);
    ShiftChild(CurrentNode->Child, False, RightIndex + 1, CurrentNode->Num);
    (CurrentNode->Num)--;
    
    if(CurrentNode == T->Root && 0 == CurrentNode->Num){
        T->Root = LeftNode;
    }
}

Source Code

#include 
#include 

#define MinDegree 4

typedef int ElementType;
typedef int* PtrElementType;

typedef enum Bool BoolType;
enum Bool{
    False = 0,
    True = 1
};

typedef struct TreeNode *PtrBpNode;
typedef struct TreeNode BpNode;
struct TreeNode{
    int Num;
    BoolType IsLeaf;
    PtrElementType Key;
    PtrBpNode *Child;
    PtrBpNode Next;
};

typedef struct Tree *PtrBp;
struct Tree{
    PtrBpNode Root;
};

PtrBpNode BpAllocateNode(BoolType IsLeaf);
void BpSpilitNode(PtrBpNode SpilitNodeP, int ChildIndex);
void BpInsertNonFull(PtrBpNode CurrentNode, ElementType Val);
void BpInsert(PtrBp T, ElementType Val);
void BpMerge(PtrBp T, PtrBpNode CurrentNode, int LeftIndex, int RightIndex);
void BpDelete(PtrBp T, PtrBpNode CurrentNode, ElementType Val);
void ShiftKey(PtrElementType Key, BoolType Direction, int Begin, int End);
void ShiftChild(PtrBpNode *Child, BoolType Direction, int Begin, int End);
int GetIndex(PtrElementType Key, int Size, ElementType Val);
void BpPrintTree(PtrBpNode Root);
void BpCreateTree(PtrBp T);

int main(){
    PtrBp T = (PtrBp)malloc(sizeof(struct Tree));
    
    T->Root = BpAllocateNode(True);
    BpCreateTree(T);
    
    //printf("B_Tree after delete 11:\n");
    //BTDelete(T, T->Root, 11);
    //BTPrintTree(T->Root);
    printf("Bp_Tree after delete 16:\n");
    BpDelete(T, T->Root, 16);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 18:\n");
    BpDelete(T, T->Root, 18);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 20:\n");
    BpDelete(T, T->Root, 20);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 19:\n");
    BpDelete(T, T->Root, 19);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 0:\n");
    BpDelete(T, T->Root, 0);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 5:\n");
    BpDelete(T, T->Root, 5);
    BpPrintTree(T->Root);
    printf("Bp_Tree after delete 2:\n");
    BpDelete(T, T->Root, 2);
    BpPrintTree(T->Root);
    
    return 0;
}

PtrBpNode BpAllocateNode(BoolType IsLeaf){
    int i;
    PtrBpNode NewNode = (PtrBpNode)malloc(sizeof(BpNode));
    
    NewNode->Num = 0;
    if(True == IsLeaf){
        NewNode->IsLeaf = True;
    }
    else{
        NewNode->IsLeaf = False;
    }
    NewNode->Key = (PtrElementType)malloc(sizeof(ElementType) * (MinDegree * 2 - 1));
    NewNode->Child =(PtrBpNode*)malloc(sizeof(PtrBpNode) * MinDegree * 2);
    for(i = 0; i 2; i++){
        NewNode->Child[i] = NULL;
    }
    NewNode->Next = NULL;
    
    return NewNode;
}

void BpInsert(PtrBp T, ElementType Val){
    PtrBpNode NewNode;
    
    if(MinDegree * 2 - 1 == T->Root->Num){
        NewNode = BpAllocateNode(False);
        NewNode->Child[0] = T->Root;
        T->Root = NewNode;
        BpSpilitNode(NewNode, 0);
    }
    
    BpInsertNonFull(T->Root, Val);
}

void BpInsertNonFull(PtrBpNode CurrentNode, ElementType Val){
    int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);
    
    if(True == CurrentNode->IsLeaf){
        ShiftKey(CurrentNode->Key, True, Index, CurrentNode->Num - 1);
        CurrentNode->Key[Index] = Val;
        (CurrentNode->Num)++;
    }
    else{
        if(MinDegree * 2 - 1 == CurrentNode->Child[Index]->Num){
            BpSpilitNode(CurrentNode, Index);
            if(CurrentNode->Key[Index]                 Index++;
            }
        }
        
        BpInsertNonFull(CurrentNode->Child[Index], Val);
    }
}

void BpSpilitNode(PtrBpNode SpilitNodeP, int ChildIndex){
    int i;
    PtrBpNode NewNode, SubNode = SpilitNodeP->Child[ChildIndex];
    
    if(True == SubNode->IsLeaf){
        NewNode = BpAllocateNode(True);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        NewNode->Num = MinDegree - 1;
        SubNode->Num = MinDegree;
        NewNode->Next = SubNode->Next;
        SubNode->Next = NewNode;
    }
    else{
        NewNode = BpAllocateNode(False);
        for(i = 0; i 1; i++){
            NewNode->Key[i] = SubNode->Key[i + MinDegree];
        }
        for(i = 0; i             NewNode->Child[i] = SubNode->Child[i + MinDegree];
        }
        NewNode->Num = SubNode->Num = MinDegree - 1;
    }
    
    ShiftKey(SpilitNodeP->Key, True, ChildIndex, SpilitNodeP->Num - 1);
    ShiftChild(SpilitNodeP->Child, True, ChildIndex + 1, SpilitNodeP->Num);
    SpilitNodeP->Key[ChildIndex] = SubNode->Key[MinDegree - 1];
    SpilitNodeP->Child[ChildIndex + 1] = NewNode;
    (SpilitNodeP->Num)++;
}

void ShiftKey(PtrElementType Key, BoolType Direction, int Begin, int End){
    int i;
    
    if(True == Direction){
        for(i = End; i >= Begin; i--){
            Key[i + 1] = Key[i];
        }
    }
    else{
        for(i = Begin; i <= End; i++){
            Key[i - 1] = Key[i];
        }
    }
}

void ShiftChild(PtrBpNode *Child, BoolType Direction, int Begin, int End){
    int i;
    
    if(True == Direction){
        for(i = End; i >= Begin; i--){
            Child[i + 1] = Child[i];
        }
    }
    else{
        for(i = Begin; i <= End; i++){
            Child[i - 1] = Child[i];
        }
    }
}

int GetIndex(PtrElementType Key, int Size, ElementType Val){
    int i;
    
    for(i = 0; i         if(Key[i] >= Val){
            break;
        }
    }
    
    return i;
}

void BpDelete(PtrBp T, PtrBpNode CurrentNode, ElementType Val){
    int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);
    PtrBpNode Precursor, SubNode, Successor;
    
    if(Index Num && Val == CurrentNode->Key[Index]){
        
        if(True == CurrentNode->IsLeaf){
            ShiftKey(CurrentNode->Key, False, Index + 1, CurrentNode->Num - 1);
            (CurrentNode->Num)--;
            return;
        }
        else{
            Precursor = CurrentNode->Child[Index];
            Successor = CurrentNode->Child[Index + 1];
            
            if(Precursor->Num >= MinDegree){
                if(True == SubNode->IsLeaf){
                    CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 2];
                }
                else{
                    CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 1];
                }
                
                BpDelete(T, Precursor, Precursor->Key[SubNode->Num - 1]);
            }
            else if(Successor->Num >= MinDegree){
                CurrentNode->Key[Index] = Successor->Key[0];
                if(True == SubNode->IsLeaf){
                    SubNode->Key[SubNode->Num - 1] = CurrentNode->Key[Index];
                }
                
                BpDelete(T, Successor, Successor->Key[0]);
            }
            else{
                BpMerge(T, CurrentNode, Index, Index + 1);
                
                BpDelete(T, Precursor, Val);
            }
        }
        
    }
    else{
        
        if(True == CurrentNode->IsLeaf){
            return;
        }
        else{
            if(Index > 0){
                Precursor = CurrentNode->Child[Index - 1];
            }
            SubNode = CurrentNode->Child[Index];
            if(Index Num){
                Successor = CurrentNode->Child[Index + 1];
            }
            
            
            if(SubNode->Num >= MinDegree){
                BpDelete(T, SubNode, Val);
            }
            else{
                if(Index > 0 && Precursor->Num >= MinDegree){
                    ShiftKey(SubNode->Key, True, 0, SubNode->Num - 1);
                    SubNode->Key[0] = CurrentNode->Key[Index - 1];
                    
                    if(True == SubNode->IsLeaf){
                        CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 2];
                    }
                    else{
                        CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 1];
                        ShiftChild(SubNode->Child, True, 0, SubNode->Num);
                        SubNode->Child[0] = Precursor->Child[Precursor->Num];
                    }
                    (SubNode->Num)++;
                    (Precursor->Num)--;
                    
                    BpDelete(T, SubNode, Val);
                }
                else if(Index Num && Successor->Num >= MinDegree){
                    if(True == SubNode->IsLeaf){
                        SubNode->Key[SubNode->Num] = Successor->Key[0];
                    }
                    else{
                        SubNode->Key[SubNode->Num] = CurrentNode->Key[Index];
                    }
                    CurrentNode->Key[Index] = Successor->Key[0];
                    SubNode->Child[SubNode->Num + 1] = Successor->Child[0];
                    (SubNode->Num)++;
                    
                    ShiftKey(Successor->Key, False, 1, Successor->Num - 1);
                    ShiftChild(Successor->Child, False, 1, Successor->Num);
                    (Successor->Num)--;
                    
                    BpDelete(T, SubNode, Val);
                }
                else{
                    if(Index > 0){
                        BpMerge(T, CurrentNode, Index - 1, Index);
                        BpDelete(T, Precursor, Val);
                    }
                    else{
                        BpMerge(T, CurrentNode, Index, Index + 1);
                        BpDelete(T, SubNode, Val);
                    }
                }
            }
        }
        
    }
}

void BpMerge(PtrBp T, PtrBpNode CurrentNode, int LeftIndex, int RightIndex){
    int i;
    PtrBpNode LeftNode = CurrentNode->Child[LeftIndex];
    PtrBpNode RightNode = CurrentNode->Child[RightIndex];
    
    if(True == LeftNode->IsLeaf){
        for(i = 0; i 1; i++){
            LeftNode->Key[i + MinDegree - 1] = RightNode->Key[i];
        }
        LeftNode->Num = MinDegree * 2 - 2;
        LeftNode->Next = RightNode->Next;
    }
    else{
        for(i = 0; i 1; i++){
            LeftNode->Key[i + MinDegree] = RightNode->Key[i];
        }
        for(i = 0; i             LeftNode->Key[i + MinDegree] = RightNode->Key[i];
        }
        LeftNode->Key[MinDegree - 1] = CurrentNode->Key[LeftIndex];
        LeftNode->Num = MinDegree * 2 - 1;
    }
    
    ShiftKey(CurrentNode->Key, False, LeftIndex + 1, CurrentNode->Num - 1);
    ShiftChild(CurrentNode->Child, False, RightIndex + 1, CurrentNode->Num);
    (CurrentNode->Num)--;
    
    if(CurrentNode == T->Root && 0 == CurrentNode->Num){
        T->Root = LeftNode;
    }
}

void BpPrintTree(PtrBpNode Root){
    int i;
    
    if(NULL == Root){
        return;
    }
    
    putchar('[');
    for(i = 0; i Num; i++){
        printf("%d", Root->Key[i]);
        if(i != Root->Num - 1){
            putchar(' ');
        }
    }
    putchar(']');
    printf("%d ", Root->IsLeaf);
    printf("%d", Root->Num);
    putchar('\n');
    
    for(i = 0; i <= Root->Num; i++){
        BpPrintTree(Root->Child[i]);
    }
}

void BpCreateTree(PtrBp T){
    int i;
    int a[] = {12,1,9,2,0,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17,20,21,23};
    
    for(i = 0; i <23; i++){
        BpInsert(T, a[i]);
        BpPrintTree(T->Root);
        printf("The End\n");
    }
}