バランスツリー(AVLツリー)作成、検索、挿入操作「大話データ構造」c++実装コード

//     ，    AVL 
#include

using namespace std;

typedef int status;

#define true 1
#define false 0

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


//          
typedef struct Bitnode
{
	int data;
	int bf;    //         
	struct Bitnode *left,*right;
}Bitnode,*Bitree;


   //  
void R_rotate(Bitree *p);
void L_rotate(Bitree *p);
void Leftbalance(Bitree *T);
void Rightbalance(Bitree *T);
status Insertavl(Bitree *T,int e,status *taller);
void Createavl(Bitree *T,int a[],int n);
void Showbst(Bitree T);       //         
   

//f  T   ， T      ，  f       Null
//    ，  p          ，  TRUE
//    ，P                ，  false
Bitree Searchavl(Bitree T,int key)
{
	if (!T) 
		return NULL;

    //     
    if (key==T->data)
        return T;
    else if (keydata)
    {
        //         
        return Searchavl(T->left,key);
    }
    else
    {
        //         
        return  Searchavl(T->right,key);
    }
}


//  p             。    p        
//             
void R_rotate(Bitree *p)
{
	Bitree L;
	L=(*p)->left;
	(*p)->left=L->right;
	L->right=*p;
	*p=L;
}

//  p             。    p        
//             
void L_rotate(Bitree *p)
{
	Bitree R;
	R=(*p)->right;
	(*p)->right=R->left;
	R->left=*p;
	*p=R;
}
//  T               
//    T        
void Leftbalance(Bitree *T)
{
	Bitree L,Lr;
	L=(*T)->left;  //L  T       
	switch(L->bf)
	{
		//  T       ，       
	case LH:  //      T         ，       
		(*T)->bf=L->bf=EH;
		R_rotate(T);
		break;
    case RH:    //      T         ，       
		Lr=L->right;  //Lr  T         
		switch(Lr->bf)
		{
		case LH: 
			(*T)->bf=RH;
			L->bf=EH;
			break;
		case EH:
			(*T)->bf=L->bf=RH;
			break;
		case RH:
			(*T)->bf=EH;
			L->bf=LH;
			break;
		}
		Lr->bf=EH;
		L_rotate(&(*T)->left);
		R_rotate(T);
	}
}


//T     ，   ，    ，   ，       R->bf
//   LH，R       ， T->rchild->bf T->bf  
void Rightbalance(Bitree *T)
{
    Bitree R,Rl;
    R = (*T)->right;
    Rl = R->left;
    switch(R->bf)
    {
        case RH:
            R->bf = (*T)->bf = EH;
            L_rotate(T);
            break;
        case LH:
            switch(R->bf)
            {
                case LH:
                    R->bf = RH;
                    (*T)->bf = EH;
                    break;
                case EH:
                    R->bf = (*T)->bf = EH;
                    break;
                case RH:
                    R->bf = EH;
                    (*T)->bf = LH;
                    break;
            }
            Rl->bf = EH;
            R_rotate(&R);
            L_rotate(T);
            break;
    }
}

//          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)->left=(*T)->right=NULL;
		(*T)->bf=EH;
		*taller=true;
	}
	else
	{
		if(e==(*T)->data)
		{
			//     e              
			*taller=false;
			return false;
		}
		if(edata)
		{
			//    t         
			if(!Insertavl(&(*T)->left,e,taller))
				return false;
			if(*taller)
			{
				switch((*T)->bf)
				{
				case LH:
					Leftbalance(T);
					*taller=false;
					break;
				case EH:
					(*T)->bf=LH;
					*taller=true;
					break;
				case RH:
					(*T)->bf=EH;
					*taller=false;
					break;
				}
			}
		}
		else
		{
			if(!Insertavl(&(*T)->right,e,taller))
				return false;
			if(*taller)
			{
				switch((*T)->bf)
				{
				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;
}

void Createavl(Bitree *T,int a[],int n)
{
	int i;
	status taller;
	for(i=0;ileft);
		cout<data<right);
	}
}

int main()
{
	int a[]={62,88,58,47,35,73,51,99,37,93};

	Bitree T=NULL;
	status taller=0;

	//       
	Createavl(&T,a,10);
	cout<data<