#include<iostream.h>
#include<iomanip.h>
typedef int KeyType;
typedef int RecType;
#define K 20
#define m 5
typedef struct BTnode
{ 
  int keynum;  
  struct BTnode *parent;
  KeyType key[m+1];
  struct BTnode *ptr[m+1];
  RecType *recptr[m+1];
}BTreeNode;
typedef BTreeNode *BTree;
BTree t=new BTreeNode[K];
int BTSearch(BTree &T,KeyType k,BTree *p);
BTree Insert(BTree &T,KeyType k);
BTree split(BTree &p);
int MoveKey(BTree &p);
BTree merge(BTree &p);
BTree  Delete(BTree &T,KeyType k);
int BTSearch(BTree &T,KeyType k,BTree *p)
{
    BTree q;
    int i;
    *p=q=T;
    while(q!=NULL)
    {
        *p=q;
        q->key[0]=k;   
        for(i=q->keynum;k<q->key[i];i--)
        if(i>0&&q->key[i]==k) 
        return i;
        q=q->ptr[i];
    }
 return 0;
}
BTree Insert(BTree &T,KeyType k)
{
 BTree p,s1=NULL,s2=NULL;
 int i;
 if(BTSearch(T,k,&p)) 
    return T;                  
 while(p!=NULL)
 {
   p->key[0]=k;            
   for(i=p->keynum;k<p->key[i];i--)
   {
       p->key[i+1]=p->key[i];
       p->ptr[i+1]=p->ptr[i];
   }
   p->key[i]=k;    
   cout<<setw(3)<<p->key[i];
   p->ptr[i-1]=s1; 
   if(++(p->keynum)<m)
     break;
   else 
   {
    s2=split(p);
    s1=p;    
    k=p->key[p->keynum+1];
    p=p->parent;
   }
  }
  if(p==NULL)
  {
      p=++t;    
      p->keynum=1;
      p->key[1]=k;
      p->ptr[0]=s1;
      p->ptr[1]=s2;
      return p;
  }
  else 
      return T;
}
int MoveKey(BTree &p)
{
    BTree b,f=p->parent,s2=NULL;     
    int i,j;
    for(i=0;f->ptr[i]!=p;i++);
    p->ptr[i]=s2;   
    if(i>0)                   
    {
        b=f->ptr[i-1];          
        if(b->keynum>(m-1)/2)   
        {
            for(j=p->keynum;j>=0;j--)
            {
                p->key[j+1]=p->key[j];
                p->ptr[j+1]=p->ptr[j];
            }
            p->key[1]=f->key[i];  
            f->key[i]=b->key[b->keynum];
            p->ptr[0]=b->ptr[b->keynum];
            p->keynum++;
            b->keynum--;    
            return 1;
        }                
        if(i<f->keynum)            
        {
            b=f->ptr[i+1];             
            if(b->keynum>(m-1)/2)      
            {
                p->key[p->keynum]=f->key[i+1];
                f->key[i+1]=b->key[1];     
                p->ptr[p->keynum]=b->ptr[0];
                for(j=0;j<b->keynum;j++)
                {
                    b->key[j]=b->key[j+1];
                    b->ptr[j]=b->ptr[j+1];
                } 
                p->keynum++;
                b->keynum--;
                return 1;
            }
        }
    }          
 return 0;
}
BTree split(BTree &p)
{
    int i,mid,j;
    t++;
    mid=(m+1)/2;
    t->ptr[0]=p->ptr[mid];
    j=1;
    for(i=mid+1;i<=m;i++)
    {
        t->key[j]=p->key[i];
        t->ptr[j++]=p->ptr[i];
    }
    t->keynum=m-mid;
    p->keynum=mid-1;
    return(t);
}
BTree merge(BTree &p)
{
    BTree b,f=p->parent;      
    int i,j;
    for(i=0;f->ptr[i]!=p;i++) ;
    if(i>0)                     
        b=f->ptr[i-1];     
    else
    {
        b=p;
        p=f->ptr[i+1];
    }          
    b->key[++b->keynum]=f->key[i];
    b->ptr[p->keynum]=p->ptr[0]; 
    for(j=1;j<=b->keynum;j++)   
    {
        b->key[++b->keynum]=p->key[j];
        b->ptr[b->keynum]=p->ptr[j];
    }
    delete p;
    for(j=i+1;j<=f->keynum;j++)
    {
        f->key[j-1]=f->key[j];
        f->ptr[j-1]=f->ptr[j];
    }
    f->keynum--;
    return b;
}
BTree Delete(BTree &T,KeyType k)
{
    BTree p,s;
    int i,j;
    i=BTSearch(T,k,&p);   
    if(i==0)
        return T; 
    if(i>0&&p->ptr[i-1]) 
    {
        s=p->ptr[i-1];       
        while(s->ptr[s->keynum])
        s=s->ptr[s->keynum];
        p->key[i]=s->key[s->keynum];
        p=s;
        i=s->keynum;
    }
    for(j=i;j<p->keynum;j++)
        p->key[j]=p->key[j+1];
        p->keynum--;
        while(p->keynum<(m-1)/2&&p->parent)
        { 
            if(!MoveKey(p)) 
            p=merge(p);  
            p=p->parent;    
        }
        if(p==T&&T->keynum==0)
        {
            T=T->ptr[0];
            delete p;
        } 
 
        return T;
}
void main()
{
    cout<<"B_Tree.cpp运行结果:\n";
    KeyType k=12;
    t->keynum=0;
    t->parent=NULL;
    t->key[0]=t->key[1]=0;
    t->ptr[0]=t->ptr[1]=NULL;
    t->recptr[0]=t->recptr[1]=NULL;
    cout<<"插入关键字:\n";
    for(int i=1;i<=k;i++)
    {
        Insert(t,2*i);
        ++t;
    }
    cout<<endl;
        for(i=2;i<=k;i+=2)
        {
            if(Delete(t,i)) cout<<"关键字"<<i<<"删除成功!\n";
            else 
                cout<<"关键字"<<i<<"删除不成功!\n";
            t++;
        }
        cin.get();
}