[데이터 구조] 밸 런 스 이 진 트 리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 (e<(*T)->data)
		{ /*      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;
}