데이터 구조 실천 - B - 트 리 의 기본 조작

본 고 는 [데이터 구조 기초 시리즈 (8): 찾기] 에 대한 실천 이다.
[프로젝트 - B - 나무의 기본 조작] B - 나무의 기본 조작 을 실현 합 니 다.시퀀스 {4, 9, 0, 1, 8, 6, 3, 5, 2, 7} 을 기반 으로 테스트 를 마 쳤 습 니 다.(1) 대응 하 는 3 단계 B - 트 리 b 를 만 들 고 b 트 리 를 괄호 로 출력 합 니 다.(2) b 에서 키워드 가 8 과 1 인 노드 를 각각 삭제 하고 노드 를 삭제 한 b 트 리 를 괄호 로 출력 한다.[참고 해답]

#include <stdio.h>
#include <malloc.h>
#define MAXM 10 //  B-       
typedef int KeyType;                //KeyType      
typedef struct node                 //B-       
{
    int keynum;                     //             
    KeyType key[MAXM];              //key[1..keynum]     ,key[0]  
    struct node *parent;            //      
    struct node *ptr[MAXM];         //        ptr[0..keynum]
} BTNode;
typedef struct                      //B-        
{
    BTNode *pt;                     //       
    int i;                          //1..m,          
    int tag;                        //1:    ,O:    
}  Result;
int m;                              //m B- ,     
int Max;                            //m B-              ,Max=m-1
int Min;                            //m B-               ,Min=(m-1)/2
int Search(BTNode *p,KeyType k)
{
    // p->key[1..keynum]   i,  p->key[i]<=k<p->key[i+1]
    int i=0;
    for(i=0; i<p->keynum && p->key[i+1]<=k; i++);
    return i;
}
Result SearchBTree(BTNode *t,KeyType k)
{
    /* m t t      k,    (pt,i,tag)。     ,     tag=1,  pt      i      k；     tag=0,  k           Pt      i  i+1      */
    BTNode *p=t,*q=NULL; //   ,p      ,q  p   
    int found=0,i=0;
    Result r;
    while (p!=NULL && found==0)
    {
        i=Search(p,k);              // p->key[1..keynum]   i,  p->key[i]<=k<p->key[i+1]
        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   (     )
}
void Insert(BTNode *&q,int i,KeyType x,BTNode *ap)
{
    // x ap     q->key[i+1] q->ptr[i+1] 
    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++;
}
void Split(BTNode *&q,BTNode *&ap)
{
    //   q       ,     ,         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
}
void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap)
{
    //     (T,x,ap)      *t, t 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;
}
void InsertBTree(BTNode *&t, KeyType k, BTNode *q, int i)
{
    /* m t t   *q key[i] key[i+1]       k。        ,                , t  m t 。*/
    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)
        {
            Insert(q,i,x,ap);               // x ap     q->key[i+1] q->ptr[i+1]
            if (q->keynum<=Max) finished=1; //    
            else
            {
                //    *q, 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)              //     *q   x     
                {
                    q=q->parent;
                    i=Search(q, x);
                }
                else needNewRoot=1;
            }
        }
        if (needNewRoot==1)                 //         *q *ap
            NewRoot(t,q,x,ap);              //      *t,q ap     
    }
}
void DispBTree(BTNode *t)   //        B- 
{
    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(")");  //          ")" 
        }
    }
}
void Remove(BTNode *p,int i)
// *p    key[i]       ptr[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--;
}
void Successor(BTNode *p,int i)
//       p->key[i](       )       
{
    BTNode *q;
    for (q=p->ptr[i]; q->ptr[0]!=NULL; q=q->ptr[0]);
    p->key[i]=q->key[1];    //      
}
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--;
}
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];
    }
}
void Combine(BTNode *p,int i)
//             
{
    int c;
    BTNode *q=p->ptr[i];            //     ,        
    BTNode *l=p->ptr[i-1];
    l->keynum++;                    //l     
    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);                        //         
}
void Restore(BTNode *p,int i)
//      ,  B- ,            p->ptr[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)   //     
        MoveRight(p,i);
    else if (p->ptr[i+1]->keynum>Min)
        MoveLeft(p,i+1);
    else
        Combine(p,i);
}
int SearchNode(KeyType k,BTNode *p,int &i)
//   p      k   i,     1,    0
{
    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]);
    }
}
int RecDelete(KeyType k,BTNode *p)
//        k
{
    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);                    // *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;
    }
}
void DeleteBTree(KeyType k,BTNode *&root)
// B- root      k,               ,        ,      
{
    BTNode *p;              //        root
    if (RecDelete(k,root)==0)
        printf("    %d  B-  
",k);
    else if (root->keynum==0)
    {
        p=root;
        root=root->ptr[0];
        free(p);
    }
}
int 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("    %d B- :
",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("
");
    }
    printf("   B- : ");
    DispBTree(t);
    printf("
");
    printf("    :
");
    k=8;
    DeleteBTree(k,t);
    printf("   %d: ",k);
    printf("B- : ");
    DispBTree(t);
    printf("
");
    k=1;
    DeleteBTree(k,t);
    printf("   %d: ",k);
    printf("B- : ");
    DispBTree(t);
    printf("
");
    return 0;
}