B_树的插入、删除操作

#include<stdio.h>
#include<malloc.h>
#define MAXM 10  //B-树最大阶数

typedef int KeyType;  //keyType是关键字类型
typedef struct node
{
 int keynum;  //当前拥有关键字个数
 KeyType key[MAXM];  //key[1,2,...,keynum]存放关键字的个数
 struct node *parent;  //双亲指针节点
 struct node *ptr[MAXM];  //孩子节点指针数组ptr[0...keynum]
}BTNode;

typedef struct  //B-树的查找结果类型
{
 BTNode *pt;  //指向找到的节点
 int i;  //i...m在节点中的关键字序号
 int tag;  //1：查找成功 0：查找失败
}Result;

int m;  //m阶B-树作为全局变量
int Max;  //m阶B-树中每个节点的最多关键字个数，Max=m-1
int Min;  //m阶B-树中非叶子节点的最少关键字个数，Min=（m-1）/2

/*1.在p->key[1...keynum]中查找i，使得p->key[i]<=k<p->key[i+1]*/
int Search(BTNode *p,KeyType k)
{
 for(int i=0; i<p->keynum && p->key[i+1]<=k; i++);
 return i;
}

/*
2.在m阶t树t上查找关键字k，返回结果（pt，i，tag）。
若查找成功，则特征值tag=1，指针pt所指节点中第i个关键字=k；
否则特征值tag=0，等于k的光剑子应该插入在指针pt所指节点中第i和第i+1个关键字之间
*/
Result SearchBTree(BTNode *t,KeyType k)
{
 BTNode *p=t,*q=NULL;  //初始化，p指向带查看节点，q指向p的双亲
 int found=0,i=0;
 Result r;
 while(p!=NULL && found==0)
 {
  /*在p->key[i..keynum]中查找i，使得p->key[i]<=k<p->key[i+1]*/
  i=Search(p,k);
  if(i>0 && p->key[i]==k)
   found=1;
  else
  {
   q=p;
   p=p->ptr[i];
  }
 }

 r.i=i;
 if(found==1)  //查找成功
 {
  r.pt=p;
  r.tag=1;
 }
 else  //查找失败，返回k的插入位置信息
 {
  r.pt=q;
  r.tag=0;
 }
 return r;  //返回k的位置，或者插入的位置
}

/*3.将x和ap分别插入到q->key[i+1]和q->ptr[i+1]中*/
void Insert(BTNode * &q,int i,KeyType x,BTNode *ap)
{
 int j;
 for(j=q->keynum; j>i; j--)  //空出一个位置
 {
  q->key[j+1]=q->key[j];
  q->ptr[j+1]=q->ptr[j];
 }
 q->key[i+1]=x;
 q->ptr[i+1]=ap;
 if(ap!=NULL)
  ap->parent=q;
 q->keynum++;
}

/*4.将节点q分裂成两个节点，前一半保留，后一半移入新生节点ap*/
void Split(BTNode * &q,BTNode * &ap)
{
 int i,s=(m+1)/2;
 ap=(BTNode *)malloc(sizeof(BTNode));  //生成新节点ap
 ap->ptr[0]=q->ptr[s];  //后一半移入ap
 for(i=s+1; i<=m; i++)
 {
  ap->key[i-s]=q->key[i];
  ap->ptr[i-s]=q->ptr[i];
  if(ap->ptr[i-s]!=NULL)
   ap->ptr[i-s]->parent=ap;
 }
 ap->keynum=q->keynum-s;
 ap->parent=q->parent;
 for(i=0; i<=q->keynum-s; i++)  //修改指向双亲节点的指针
  if(ap->ptr[i]!=NULL)
   ap->ptr[i]->parent=ap;
  q->keynum=s-1;  //q的前一半保留，修改keynum
}

/*5.生成含信息（t，x，ap）的新的根结点*t，原t和ap为子树指针*/
void NewRoot(BTNode * &t,BTNode *p,KeyType x,BTNode *ap)
{
 t=(BTNode *)malloc(sizeof(BTNode));
 t->keynum=1; t->ptr[0]=p; t->ptr[1]=ap; t->key[1]=x;
 if(p!=NULL) p->parent=t;
 if(ap!=NULL) ap->parent=t;
 t->parent=NULL;
}

/*
6.在m阶t树t上结点*q的key[i]与key[i+1]之间插入关键字k。
若引起结点过大，则沿双亲链进行必要的节点分裂调整，使得t荏苒是m阶t树
*/
void InsertBTree(BTNode * &t,KeyType k,BTNode *q,int i)
{
 BTNode *ap;
 int finished,needNewRoot,s;
 KeyType x;
 if(q==NULL)  //t是空树，参数q的初值为NULL
  NewRoot(t,NULL,k,NULL);  //生成仅含关键字k的根节点*t
 else
 {
  x=k; ap=NULL; finished=needNewRoot=0;
  while(needNewRoot==0 && finished==0)
  {
   /*将x和ap分别插入到q->key[i+1]he q->ptr[i+1]*/
   Insert(q,i,x,ap);
   if(q->keynum<=Max) finished=1;  //插入完成
   else
   {
    /*
    分裂节点*p，将q->key[s+1..m]，q->ptr[s..m]
        和q->recptr[s+1..m]移入新结点*ap
    */
    s=(m+1)/2;
    Split(q,ap);
    x=q->key[s];
    if(q->parent)  //在双亲节点*p中查找x的插入位置
    {
     q=q->parent;
     i=Search(q,x);
    }
    else
     needNewRoot=1;
   }
  }
  if(needNewRoot==1)  //根结点已经分裂成为结点*q和*ap
   NewRoot(t,q,x,ap);  //生成新节点*t，q和ap为子树指针
 }
}

/*7以括号表示法输出B-树*/
void DispBTree(BTNode *t)
{
 int i;
 if(t!=NULL)
 {
  printf("[");  //输出当前节点关键字
  for(i=1; i<t->keynum; i++)
   printf("%d",t->key[i]);
  printf("%d",t->key[i]);
  printf("]");
  if(t->keynum>0)
  {
   if(t->ptr[0]!=0) printf("(");  //至少有一个子树时输出“(”号
   for(i=0; i<t->keynum; i++)  //对每个子树进行递归调用
   {
    DispBTree(t->ptr[i]);
    if(t->ptr[i+1]!=NULL) printf(",");
   }
   DispBTree(t->ptr[t->keynum]);
   if(t->ptr[0]!=0) printf(")");  //至少有一个子树时输出")"号
  }
 }
}

/*8.从结点p删除key[i]和它的孩子指针ptr[i]*/
void Remove(BTNode *p,int i)
{
 int j;
 for(j=i+1; j<=p->keynum; j++)  //前移删除key[i]和ptr[i]
 {
  p->key[j-1]=p->key[j];
  p->ptr[j-1]=p->ptr[j];
 }
 p->keynum--;
}

/*9.查找被删除关键字p->key[i](在非叶子结点中)的替代叶子结点*/
void Successor(BTNode *p,int i)
{
 BTNode *q;
 for(q=p->ptr[i]; q->ptr[0]!=NULL; q=q->ptr[0]);
 p->key[i]=q->key[1];  //复制关键字值
}

/*10.把一个关键字移动到右兄弟中*/
void MoveRight(BTNode *p,int i)
{
 int c;
 BTNode *t=p->ptr[i];
 for(c=t->keynum; c>0; c--)
 {
  t->key[c+1]=t->key[c];
  t->ptr[c+1]=t->ptr[c];
 }
 t->ptr[1]=t->ptr[0];  //从双亲结点移动关键字到右兄弟中
 t->keynum++;
 t->key[1]=p->key[i];
 t=p->ptr[i-1];  //将左兄弟中最后一个关键字移动到双亲节点中
 p->key[i]=t->key[t->keynum];
 p->ptr[i]->ptr[0]=t->ptr[t->keynum];
 t->keynum--;
}

/*11.把一个关键字移动的左兄弟中*/
void MoveLeft(BTNode *p,int i)
{
 int c;
 BTNode *t;
 t=p->ptr[i-1];  //把双亲结点中的关键字移动到双亲节点中
 t->keynum++;
 t->key[t->keynum]=p->key[i];
 t->ptr[t->keynum]=p->ptr[i]->ptr[0];
 t=p->ptr[i];  //把右兄弟中的关键字移动到双亲结点中
 p->key[i]=t->key[1];
 p->ptr[0]=t->ptr[1];
 t->keynum--;
 for(c=1; c<=t->keynum; c++)  //将右兄弟中的所有关键字移动一位
 {
  t->key[c]=t->key[c+1];
  t->ptr[c]=t->ptr[c+1];
 }
}

/*12.将3个结点合并到一个节点中*/
void Combine(BTNode *p,int i)
{
 int c;
 BTNode *q=p->ptr[i];  //指向右结点，它将被置空和删除
 BTNode *l=p->ptr[i-1];
 l->keynum++;
 l->key[l->keynum]=p->key[i];
 l->ptr[l->keynum]=q->ptr[0];
 for(c=1; c<=q->keynum; c++)  //插入右结点中的所有关键字
 {
  l->keynum++;
  l->key[l->keynum]=q->key[c];
  l->ptr[l->keynum]=q->ptr[c];
 }
 for(c=i; c<p->keynum; c++)  //删除父结点的所有关键字
 {
  p->key[c]=p->key[c+1];
  p->ptr[c]=p->ptr[c+1];
 }
 p->keynum--;
 free(q);  //释放空右结点的空间
}

/*13.关键字删除以后，调整B-树，找到一个关键字将其插入到p->ptr[i]中*/
void Restore(BTNode *p,int i)
{
 if(i==0)  //在最左边关键字的情况
  if(p->ptr[1]->keynum>Min)
   MoveLeft(p,1);
  else
   Combine(p,1);
 else if(i==p->keynum)  //最右边关键字情况
  if(p->ptr[i-1]->keynum>Min)
   MoveRight(p,i);
  else
   Combine(p,i);
 else if(p->ptr[i-1]->keynum>Min)  //其它情况
  MoveLeft(p,i);
 else if(p->ptr[i+1]->keynum>Min)
  MoveLeft(p,i+1);
 else
  Combine(p,i);
}

/*14.在结点p中找关键字为k的位置i，成功时返回1，失败返回0*/
int SearchNode(KeyType k,BTNode *p,int &i)
{
 if(k<p->key[1])  //k小于*p结点的最小关键字时返回0
 {
  i=0;
  return 0;
 }
 else  //在*p结点中查找
 {
  i=p->keynum;
  while(k<p->key[i] && i>1)
   i--;
  return(k==p->key[i]);
 }
}

/*15.查找并删除关键字k*/
int RecDelete(KeyType k,BTNode *p)
{
 int i;
 int found;
 if(p==NULL)
  return 0;
 else
 {
  if((found=SearchNode(k,p,i)==1))  //查找关键字k
  {
   if(p->ptr[i-1]!=NULL)  //若为非叶子结点
   {
    Successor(p,i);  //由其它后继代替它
    RecDelete(p->key[i],p->ptr[i]);  //p->key[i]在叶子结点中
   }
   else
    Remove(p,i);
  }
  else
   found=RecDelete(k,p->ptr[i]);  //沿孩子结点递归查找并删除关键字k
  if(p->ptr[i]!=NULL)
   if(p->ptr[i]->keynum<Min)  //删除后关键字个数小于Min
     Restore(p,i);
   return found;
 }
}

/*16.从B-树root中删除关键字k，若在一个结点中删除指定的关键字，不再有其它关键字，则删除该结点*/
void DeleteBTree(KeyType k,BTNode * &root)
{
 BTNode *p;  //用于释放一个空的root
 if(RecDelete(k,root)==0)
  printf("  关键字 %d 不在B-树中\n",k);
 else if(root->keynum==0)
 {
  p=root;
  root=root->ptr[0];
  free(p);
 }
}

void main()
{
 BTNode *t=NULL;
 Result s;
 int j,n=10;
 KeyType a[]={4,9,0,1,8,6,3,5,2,7},k;
 m=3;  //3阶B+树
 Max=m-1;
 Min=(m-1)/2;
 printf("\n创建一颗 %d 阶B-树:\n",m);
 for(j=0; j<n; j++)  //创建一颗3阶B-树t
 {
  s=SearchBTree(t,a[j]);
  if(s.tag==0)
   InsertBTree(t,a[j],s.pt,s.i);
  printf("第 %d 步，插入 %d:",j+1,a[j]);
  DispBTree(t);
  printf("\n");
 }

 printf("删除操作:\n");
 k=8;
 DeleteBTree(k,t);
 printf("删除 %d ",k);
 DispBTree(t);
 printf("\n");
 k=1;
 DeleteBTree(k,t);
 printf("删除 %d ",k);
 DispBTree(t);
 printf("\n\n");

}

//转载自http://leeocean2004.blog.163.com/blog/static/1201934320082181020739/