B树的删除操作

B树的删除操作：

对于一颗度为n的B树,它的关键字删除操作，需要考虑删除关键字后，节点是否还能继续保持B树的性质，如果节点拥有n-1个关键字，那么直接删除关键字的话会导致破坏B树节点关键字最小数目的限制。如果对于非叶子节点直接删除关键字，那么会影响子节点指针数组的组成，破坏了子节点指针结构。所以来说最好的办法就是把删除的关键字设法移动到叶子节点中去删除，因为叶子节点没有子节点指针数组，并且这个叶子节点的关键字数目要求至少是n,这样才能保证成功的删除关键字。

删除关键字的算法借鉴了http://blog.chinaunix.net/uid-20196318-id-3030529.html，自己重新实现了一下，自己的代码很丑。

Blog中描述的B树删除关键字的算法：（以下假设树的度是3）

1.删除的关键字在叶子节点中，直接在叶子节点中删除关键字，后面的两部会保证该叶子节点关键字的个数至少为n个。

2.如果删除的关键字在非叶子节点x中，x的数组下标为i

a.如果x的左孩子节点存在，x->child[i]，并且x->child[i]的节点关键字个数至少是n个，则找到 child[i]中最大的关键字max替换x中删除的关键字，继续递归child[i]删除关键字max。

说明：左侧节点红色代表3是递归删除的新的关键字

b.如果x的右孩子节点存在，x->child[i+1]，并且x->child[i+1]的节点关键字个数至少是n个，则找到 child[i+1]中最小的关键字min替换x中删除的关键字，继续递归child[i+1]删除关键字min。

c.如果x的左孩子和右孩子关键字数目都是n-1,那么这个时候应该把这个关键字和自己的左右孩子节点做合并操作（反向的分裂节点操作），继续递归删除合并节点中的关键字。

3.如果删除的关键字不再非叶子节点x中，在x节点的子节点的分支中child[i]中,且child[i]的关键字个数是n-

a.如果child[i-1]存在，并且关键字数目至少是n，那么从child[i-1]选出最大的关键字，替换x中关键字，同时这个x中的老的关键字插入到child[i]中第一个，这时child[i-1]中由于最大的关键字被移动到了父节点，这是它的子节点指针会多一个，这时从child[i-1]中删除它，正好放到child[i]子节点指针数组的第一个位置，来适应child[i]中新加入的父节点的关键字。

这个过程比较复杂，文字不好理解，如图：

说明：上图中，假设可以确定要删除的关键字在5，6分支中，那么这个分支的关键字的数量是2个（假设树的度是3），那么这个情况就不能保证case1中，如果是叶子节点直接删除关键字的说法了，所以这个时候要保证5，6分支中的关键字从别的兄弟节点中借一个。默认先从左兄弟开始借（也可以从右兄弟开始借，不成功再左兄弟）。正确的借关键字的做法就是从左（1，2，3节点）兄弟中踢掉最右侧的关键字和最右侧的子节点指针，把这个关键字（图中是3）放到父节点的4的位置上，同时把4节点放到5，6分支中，并且那个被左兄弟踢掉的子节点指针过渡到了5，6分支的第一个子节点指针的位置上。上图中红色的部分代表被移动的数据结构。

b.如果上一步失败了（左兄弟的关键字个数不够n个，或者左兄弟节点根本不存在），那么就从child[i+1]中删除第一个关键字和第一个子节点指针，关键字替代父节点的关键字，child[i]中在最后增加父节点的关键字和child[i+1]的子节点指针。类似第一步

c.如果上一步也失败了（表示从左右兄弟不能借到关键字），这时就需要child[i]和child[i-1]或者是child[i+1](child[i-1],child[i+1]至少有个子节点存在)合并到一起（如果左右兄弟节点都存在的话，合并的顺序可以随意，但是如果其中一个兄弟节点为空，为空是因为关键字是节点最后一个，或者是第一个关键字，这样就只能 合并那个存在的兄弟节点），这个过程就是B树插入关键字的逆操作，然后在递归删除这个合并节点中的关键字。

说明：上图中的情况，查找关键字在4，5分支中，但是左右兄弟都是n-1个关键字，这是兄弟把4，5兄弟节点1，2（左兄弟合并到4，5节点上）。

代码：

void deleteData(page* p,int value){
        int index=0;
        for(;index<sizeof(p->data)/sizeof(int);index++){
                if(p->data[index]==0||p->data[index]>=value)
                        break;
        }
        page* replace=p->child[index];
        if(p->data[index]!=value){  //case3
                if(pageSize(replace)==DU-1){
                        page* prev=(index==0?NULL:p->child[index-1]);
                        page* next=(index==2*DU-1?NULL:p->child[index+1]);
                        if(pageSize(prev)>DU-1){//case3-a 从左兄弟借关键字
                                int t=p->data[index-1];
                                int mIndex=maxIndex(prev);
                                page* moveChild=prev->child[mIndex+1];
                                int moveValue=prev->data[mIndex];
                                prev->data[mIndex]=0;
                                prev->child[mIndex+1]=NULL;
                                p->data[index-1]=moveValue;
                                shiftRight(replace,0,1);
                                replace->data[0]=t;
                                replace->child[0]=moveChild;
                                if(moveChild!=NULL)
                                        moveChild->parent=replace;

                        }else if(pageSize(next)>DU-1){
                                 //case3-b 从右兄弟借关键字
                                int t=p->data[index];
                                page* moveChild=next->child[0];
                                int moveValue=next->data[0];
                                shiftLeft(next,0,1);
                                p->data[index]=moveValue;
                                int mIndex=maxIndex(replace);
                                replace->data[mIndex+1]=t;
                                replace->child[mIndex+2]=moveChild;
                                if(moveChild!=NULL)
                                        moveChild->parent=replace;
                        }else{
                                //case3-c
                                if(prev!=NULL){ //合并左兄弟
                                        prev->data[DU-1]=p->data[index-1];
                                        int bi=DU;
                                        shiftLeft(p,index-1,1);
                                        int startCopy=0;
                                        //copy 关键字和子节点指针到prev
                                        for(;startCopy<2*DU-1;startCopy++){
                                                if(replace->data[startCopy]==0)
                                                        break;
                                                prev->data[bi]=replace->data[startCopy];
                                              prev->child[bi]=replace->child[startCopy];
                                                bi++;
                                        }
                                        prev->child[bi]=replace->child[startCopy];
                                        replace=prev;
                                        p->child[index-1]=prev;
                                        updateParent(replace,prev);//递归删除子节点
                                }else{   //合并右兄弟
                                        shiftRight(next,0,3);
                                        next->data[DU-1]=p->data[index];
                                        shiftLeft(p,0,1);
                                        int startCopy=0;
                                        for(;startCopy<DU-1;startCopy++){
                                         next->data[startCopy]=replace->data[startCopy];
                                       next->child[startCopy]=replace->child[startCopy];
                                        }
                                        //差一个节点没有copy
                                       next->child[startCopy]=replace->child[startCopy];
                                        replace=next;
                                        updateParent(replace,next);
                                }
                                if(pageSize(p)==0){  //如果当前节点没有关键字了，replace就是根节点
                                        root=replace;
                                        root->parent=NULL;
                                }

                        }
                }
                deleteData(replace,value); //递归删除子节点
                return;
        }
        if(p->isLeaf){  //case1   是叶子节点直接左移删除关键字
                shiftLeft(p,index,1);
        }else{ //case2
                page* replace;
                int newValue;
                if(pageSize(p->child[index])>DU-1){//case2-a
                        newValue=maxValue(p->child[index]);
                        replace=p->child[index];
                        p->data[index]=newValue;
                }else if(pageSize(p->child[index+1])>DU-1){ //case2-b
                        newValue=p->child[index+1]->data[0];
                        replace=p->child[index+1];
                        p->data[index]=newValue;
                }else{ //case2-c 合并两个子节点
                        int startCopy=DU;
                        page* prev=p->child[index];
                        page* next=p->child[index+1];
                        prev->data[DU-1]=value;
                        prev->child[2*DU-1]=next->child[DU-1];
                        int n=0;
                        for(;startCopy<2*DU-1;startCopy++){
                                prev->data[startCopy]=next->data[n];
                                prev->child[startCopy]=next->child[n] ;
                                n++;
                        }
                        shiftLeft(p,index,1);
                        p->child[index]=prev;
                        replace=prev;
                        newValue=value;
                        if(pageSize(p)==0){
                                root=replace;
                                root->parent=NULL;
                        }
                        updateParent(next,prev);    //更新父子节点关系
                }
                deleteData(replace,newValue);  //递归删除子节点

        }
}

void updateParent(page* old,page* new){
        int i=0;
        for(;i<2*DU;i++){
                if(old->child[i]==NULL)
                        break;
                old->child[i]->parent=new;
        }
}

B+树的删除，正在研究