B-树

B-树又称为多路平衡查找树，是一种组织和维护外存储文件系统非常有效的数据结构。B-树中所有结点的孩子结点的最大值被称为B-树的阶，通常用m表示，B-树满足以下条件：
树中每个结点至多有m个孩子结点，至多有m-1个关键字
除根结点外，其他结点至少有(m+1)/2个孩子结点
若根结点不是叶子结点，则根结点至少有两个孩子结点
每个结点的结如下： n p0 k1 p1 k2 p2 ... kn pn 其中，n代表是关键字个数，p指孩子结点，k指关键字集合
所有叶子结点都在同一层

B-树的构造
从一个空树开始，可以通过不断地插入关键字来构造B-树，将关键字k插入到B-树的过程可以分如下两步来完成：1）先找到关键字的插入结点位置；2）判断该结点是否还有空位置，若有空位置，直接把关键字k插入到该结点的合适位置上，如果没有空位置，将关键字k插入该结点的合适位置上，并将该结点分裂成两个，一部分包含前一半关键字，另一部分包含后一半关键字，两部分都不包括中间关键字，将中间关键字上移，移到父亲结点中，如果父亲结点的关键字个数也超过Max, 那要进行再分裂，再住上插，直到传到根结点为止。

B-树结点的删除
在B-伤残人上删除关键字k的过程如下：
1)找到关键字所在的结点；2)判断该结点是否是叶子结点，如果是非叶子结点，找到大于k的最小关键字k1，用k1将k代替，之后删除k1关键字；如果是叶子结点，判断被删结点的关键字个数，如果大于Min,可直接删去关键字k, 如果等于Min, 说明删除关键字后将不满足B-树的定义，那就看该结点的左（或右）兄弟结点中关键字个数是否大于Min, 如果有，那就把该结点的左（或右）兄弟结点中最大（或最小）关键字上移到双亲结点中，同时把双亲结点中大于（或小于）上移关键字的关键字下移到要删除的关键字结点中，如果两个兄弟结点中的关键字也都等于Min, 那这样就要把要删除关键字的结点以及左（或右）兄弟结点及双亲结点中分割二者的关键字合并成一个结点，如果这样做使双亲结点关键字个数小于Min, 那就对双亲结点做同样处理，有可能直到根结点，交使整个树减少一层。下面是实现B-树构造、删除、搜索的算法。

实现B-树的构造与删除算法
#include<iostream>
using namespace std;

typedef int KeyType; //B-树的结点类型
#define MAXV 10 //B-树结点的容量
#define M 5 //B-树结点最多能容纳的关键字个数
#define MIN (M+1)/2-1 //B-树结点最小容纳的关键字个数
typedef struct node
{
int keynum;
KeyType key[MAXV];
struct node *parent;
struct node *childs[MAXV];
}BMinusNode; //B-树结点，包括容量的关键字个数 ，子结点，父结点，及关键字

typedef struct
{
BMinusNode *pt;
int index;
bool tag;
}Result; //B-树搜索时返回的结果，pt代表所在的结点，index是在关键字序列中所处的位置，tag代表是否找得到

//将结点origin分拆为两个结点origin和createnew,
void split(BMinusNode*& origin, BMinusNode*& createnew)
{
int i;
createnew=(BMinusNode*)malloc(sizeof(BMinusNode));
createnew->parent=origin->parent;
createnew->keynum=(M-1)/2;

for(i=0;i<createnew->keynum;i++)
createnew->key[i]=origin->key[i+(M+1)/2];
for(i=0;i<createnew->keynum+1;i++)
{
createnew->childs[i]=origin->childs[i+(M+1)/2];
if(createnew->childs[i]!=NULL)
createnew->childs[i]->parent=createnew;
}

origin->keynum=(M-1)/2;
}

//向结点node插入k及新建结点newcreate
void insertBMinusNode(BMinusNode* node, KeyType k,BMinusNode* newcreate)
{
int pos=0,i;
while(pos<node->keynum)
{
if(node->key[pos]>k)
break;
pos++;
} //找到待插入的位置

node->keynum++;
for(i=node->keynum-1;i>pos;i--)
node->key[i]=node->key[i-1]; //pos后的关键字后移
node->key[pos]=k;

for(i=node->keynum;i>pos+1;i--)
node->childs[i]=node->childs[i-1]; //pos+1后的子结点后移
node->childs[pos+1]=newcreate;
if(newcreate!=NULL)
newcreate->parent=node;
}

//创建一个根结点，并将k插入其关键字序列中
void newRoot(BMinusNode*& node, KeyType k)
{
node=(BMinusNode*)malloc(sizeof(BMinusNode));
node->keynum=1;
node->key[0]=k;
for(int i=0;i<node->keynum+1;i++)
node->childs[i]=NULL;
node->parent=NULL;
}

//从结点p找值为k的关键字，若找到，返回真；pos是引用类型，表示所处的位置
bool findPos(BMinusNode* p, KeyType k,int& pos)
{
pos=0;
while(pos<p->keynum)
{
if(p->key[pos]==k)
return true;
else if(p->key[pos]>k)
break;
pos++;
}

return false;
}

//向node为头结点的B-树中插入一个值为k的关键字
void insertBMinusTree(BMinusNode*& node, KeyType k)
{
int i,j,pos;
KeyType mid;

if(node==NULL)
{
newRoot(node, k);
return;
} //创建一个根结点

BMinusNode* p=node,*q,*newcreate;

while(p!=NULL)
{
if(findPos(p,k,pos))
return;

q=p;
p=p->childs[pos];
} //找寻到叶子结点，使p->key[pos]>k且p->key[pos-1]<k

newcreate=NULL;
insertBMinusNode(q,k,newcreate); //插入到叶子结点的关键字序列中
while(q->parent!=NULL) //如果不是根结点
{
if(q->keynum!=M)
return;

mid=q->key[(M+1)/2-1];

split(q,newcreate); //将结点分裂为两个结点
q=q->parent;
insertBMinusNode(q,mid,newcreate); //将新产生的结点及中间值插入到父结点中
}

if(q->keynum!=M) //如果根结点的关键字数量满足要求
return;

mid=q->key[(M-1)/2]; //如果根结点的关键字数量不满足要求，须进行分裂，并创建一个新的根结点
split(q,newcreate);
BMinusNode* root=NULL;
newRoot(root,mid);
root->childs[0]=q;
root->childs[1]=newcreate;
q->parent=root;
newcreate->parent=root;
node=root;
}

//B-树的显示，深度优先
void dispBMinusTree(BMinusNode* root)
{
int i;
for(i=0;i<root->keynum;i++)
cout<<root->key[i]<<" ";
cout<<"/n";
for(i=0;i<root->keynum+1;i++)
{
if(root->childs[i]!=NULL)
dispBMinusTree(root->childs[i]);
}
}

//搜索B-树，看有无含值 为k的关键字
Result searchBMinusTree(BMinusNode* node, KeyType k)
{
int i;
Result res;

if(node==NULL)
{
res.pt=node;
res.index=-1;
res.tag=false;
return res;
}

i=0;
while(i<node->keynum)
{
if(node->key[i]==k)
{
res.pt=node;
res.index=i;
res.tag=true;
return res;
}
else if(node->key[i]>k)
break;
i++;
}

searchBMinusTree(node->childs[i],k);
}

//将B-树占用的空间释放
void freeBMinusTree(BMinusNode* q)
{
if(q==NULL)
return;

BMinusNode* p[MAXV];
int total;
for(int i=0;i<q->keynum+1;i++)
{
p[i]=q->childs[i];
total++;
}

delete q;

for(int i=0;i<total;i++)
freeBMinusTree(p[i]);
}

//找寻当前结点current的左右兄弟结点，leftoright为真，返回左兄弟结点，为假，返回右兄弟结点，key代表是在父结点中分割当前结点与右孩子结点的值
BMinusNode* findbrother(BMinusNode *current,bool leftoright,int& key)
{
KeyType max=current->key[current->keynum-1]; //当前结点的最大值
int pos=0;
BMinusNode *parent=current->parent;

findPos(parent, max, pos);
key=parent->key[pos];

if((pos==0&&leftoright)||(pos==parent->keynum&&leftoright))
return NULL;

if(leftoright)
return parent->childs[pos-1];
else
return parent->childs[pos+1];
}

//父亲结点parent中位置为pos的值下放到子结点pos中
void parentnodedown(BMinusNode *parent, BMinusNode *child, int pos,bool leftoright)
{
int i;
if(leftoright)
{
for(i=child->keynum+1;i>0;i--)
child->key[i]=child->key[i-1];
child->key[0]=parent->key[pos];
child->keynum++; //下放到child子结点的最前面
}
else
{
child->keynum++;
child->key[child->keynum-1]=parent->key[pos-1]; //下放到child子结点的最后面
}
}

//将结点p的pos位置的关键字删除
void removeNode(BMinusNode *&p,int pos)
{
int j;

if(p->parent==NULL&&p->keynum==1)
{
p->childs[0]->parent=NULL;
delete p;
p=NULL;
return;
} //如果当前是根结点

for(j=pos;j<p->keynum-1;j++)
p->key[j]=p->key[j+1];
for(j=pos+1;j<p->keynum;j++)
p->childs[j]=p->childs[j+1];
p->keynum--;
}

//子结点中的元素上浮，父亲结点的下降
void childup(BMinusNode *brother, BMinusNode *current,bool leftoright)
{
KeyType temp;
if(leftoright)
temp=brother->key[brother->keynum-1];
else
temp=brother->key[0];

int pos=0;
BMinusNode *parent=brother->parent;

findPos(parent,temp,pos);

parentnodedown(parent,current,pos,leftoright);

if(leftoright)
{
parent->key[pos]=temp;
removeNode(brother,brother->keynum-1); //左孩子的最大关键字上浮
}
else
{
parent->key[pos-1]=temp;
removeNode(brother,0); //右孩子的最大关键字上浮
}
}

//将right结点及关键字k合并到left结点中
void mergechilds(BMinusNode *left, BMinusNode* right, KeyType k)
{
int i;
left->key[left->keynum]=k;

for(i=0;i<right->keynum;i++)
left->key[i+left->keynum+1]=right->key[i];

for(i=0;i<right->keynum+1;i++)
left->childs[i+left->keynum+1]=right->childs[i];

left->keynum++;
left->keynum+=right->keynum;

delete right;
}

//将当前结点与值为key的关键字及左兄弟结点left或右兄弟结点right合并 ，优先合并左兄弟结点
void mergebrother(BMinusNode *&current,BMinusNode *left, BMinusNode *right,KeyType key)
{
if(left!=NULL)
{
mergechilds(left,current,key);
current=left;
}
else if(right!=NULL)
mergechilds(current,right,key);
else
return;
}

//将p与left或right及temp合并
void combine(BMinusNode *&p, BMinusNode* left, BMinusNode* right, KeyType temp)
{
int pos=0;

findPos(p->parent, temp,pos);

if(left!=NULL)
{
temp=p->parent->key[pos-1];
removeNode(p->parent,pos-1);
}
else
removeNode(p->parent,pos); //与左兄弟及右兄弟合并时方法不一样，temp值不一样

mergebrother(p,left,right,temp);
}

//从要结点中删去关键字为k的结点
void delBMinusNode(BMinusNode *&root, KeyType k)
{
int i,j,pos;
KeyType temp;
bool finded=false;

if(root==NULL)
return;

if(root->keynum==0)
delete root;

BMinusNode* p=root,*q,*left,*right,*s;

while(p!=NULL)
{
if(finded=findPos(p,k,pos))
break;

q=p;
p=p->childs[pos];
} //寻找包括关键字k的结点
if(!finded)
return;

if(p->childs[pos]==NULL) //如果是叶子结点
{
removeNode(p,pos);
while(p!=NULL&&p->keynum<MIN) //如果不为根结点，且不漢足要求
{
left=findbrother(p,true,temp);
right=findbrother(p,false,temp); //分别求其左右兄弟结点
if(left!=NULL&&left->keynum>MIN)
{
childup(left, p,true); //左兄弟最大关键字上浮，父亲相关关键字下来
return;
}
else if(right!=NULL&&right->keynum>MIN)
{
childup(right,p,false); //右兄弟最小关键字上浮，父亲相关关键字下来
return;
}
else
{
combine(p,left,right,temp); //左，右兄弟，及temp，当前结点合并，并将temp关键字从父结点中删去
if(p->parent==NULL) root=p;
p=p->parent;
}
}
}
else //如果删除的是非叶子结点
{
q=p->childs[pos+1];
while(q!=NULL)
{
s=q;
q=q->childs[0];
} //找到非叶子结点右侧的最小关键字
temp=s->key[0];
delBMinusNode(s,temp); //删除找到的最小关键字
p->key[pos]=temp; //用最小关键字将非叶子结点替代
}
}

int main()
{
cout<<"contrust a BMinus Tree:/n";
KeyType input;
BMinusNode* root=NULL;
while(cin>>input,input)
{
insertBMinusTree(root,input);
dispBMinusTree(root); cout<<"/n";
}

cout<<"delete BMinus Node:/n";
while(cin>>input, input)
{
delBMinusNode(root,input);
dispBMinusTree(root); cout<<"/n";
}
freeBMinusTree(root);
return 0;
}