밸런스 두 갈래 나무AVLTree

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /*           */

typedef int Status;    /* Status      ,           ， OK  */ 


/*                */
typedef  struct BiTNode    /*      */
{
    int data;    /*      */
    int bf; /*          */ 
    struct BiTNode *lchild, *rchild;    /*        */
} BiTNode, *BiTree;


/*   p             ， */
/*     p        ，                */
void R_Rotate(BiTree *P)
{ 
    BiTree L;
    L=(*P)->lchild; /*  L  P        */ 
    (*P)->lchild=L->rchild; /*  L       P     */ 
    L->rchild=(*P);
    *P=L; /*  P        */ 
}

/*   P             ， */
/*     P        ，               0  */
void L_Rotate(BiTree *P)
{ 
    BiTree R;
    R=(*P)->rchild; /*  R  P        */ 
    (*P)->rchild=R->lchild; /* R       P     */ 
    R->lchild=(*P);
    *P=R; /*  P        */ 
}

#define LH +1 /*     */ 
#define EH 0  /*     */ 
#define RH -1 /*     */ 

/*      T                   */
/*        ，  T        */
void LeftBalance(BiTree *T)
{ 
    BiTree L,Lr;
    L=(*T)->lchild; /*  L  T        */ 
    switch(L->bf)
    { /*    T        ，         */ 
         case LH: /*        T         ，        */ 
            (*T)->bf=L->bf=EH;
            R_Rotate(T);
            break;
         case RH: /*        T         ，       */ 
            Lr=L->rchild; /*  Lr  T          */ 
            switch(Lr->bf)
            { /*    T           */ 
                case LH: (*T)->bf=RH;
                         L->bf=EH;
                         break;
                case EH: (*T)->bf=L->bf=EH;
                         break;
                case RH: (*T)->bf=EH;
                         L->bf=LH;
                         break;
            }
            Lr->bf=EH;
            L_Rotate(&(*T)->lchild); /*   T            */ 
            R_Rotate(T); /*   T        */ 
    }
}

/*      T                  ， */ 
/*        ，  T        */ 
void RightBalance(BiTree *T)
{ 
    BiTree R,Rl;
    R=(*T)->rchild; /*  R  T        */ 
    switch(R->bf)
    { /*    T        ，         */ 
     case RH: /*        T         ，        */ 
              (*T)->bf=R->bf=EH;
              L_Rotate(T);
              break;
     case LH: /*        T         ，       */ 
              Rl=R->lchild; /*  Rl  T          */ 
              switch(Rl->bf)
              { /*    T           */ 
                case RH: (*T)->bf=LH;
                         R->bf=EH;
                         break;
                case EH: (*T)->bf=R->bf=EH;
                         break;
                case LH: (*T)->bf=EH;
                         R->bf=RH;
                         break;
              }
              Rl->bf=EH;
              R_Rotate(&(*T)->rchild); /*   T            */ 
              L_Rotate(T); /*   T        */ 
    }
}

/*            T     e         ，      */ 
/*       e    ，   1，    0。            */ 
/*      ，        ，    taller  T    。 */
Status InsertAVL(BiTree *T,int e,Status *taller)
{  
    if(!*T)
    { /*       ， “  ”， taller TRUE */ 
         *T=(BiTree)malloc(sizeof(BiTNode));
         (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;
         *taller=TRUE;
    }
    else
    {
        if (e==(*T)->data)
        { /*        e               */ 
            *taller=FALSE; return FALSE;
        }
        if (edata)
        { /*      T          */ 
            if(!InsertAVL(&(*T)->lchild,e,taller)) /*      */ 
                return FALSE;
            if(*taller) /*       T         “  ” */ 
                switch((*T)->bf) /*    T     */ 
                {
                    case LH: /*            ，         */ 
                            LeftBalance(T);    *taller=FALSE; break;
                    case EH: /*     、     ，             */ 
                            (*T)->bf=LH; *taller=TRUE; break;
                    case RH: /*            ，  、      */  
                            (*T)->bf=EH; *taller=FALSE; break;
                }
        }
        else
        { /*      T          */ 
            if(!InsertAVL(&(*T)->rchild,e,taller)) /*      */ 
                return FALSE;
            if(*taller) /*      T        “  ” */ 
                switch((*T)->bf) /*    T     */ 
                {
                    case LH: /*            ，  、      */ 
                            (*T)->bf=EH; *taller=FALSE;    break;
                    case EH: /*     、     ，              */
                            (*T)->bf=RH; *taller=TRUE; break;
                    case RH: /*            ，         */ 
                            RightBalance(T); *taller=FALSE; break;
                }
        }
    }
    return TRUE;
}

int main(void)
{    
    int i;
    int a[10]={3,2,1,4,5,6,7,10,9,8};
    BiTree T=NULL;
    Status taller;
    for(i=0;i<10;i++)
    {
        InsertAVL(&T,a[i],&taller);
    }
    printf("                  ");
    return 0;
}