浙大データ構造練習問題ノート:04-樹5 Root of AVL Tree(25分)

#include 
#include 
 
typedef struct AVLNode *AVLTree;
struct AVLNode{
	int data;     //    
	AVLTree left;  //     
	AVLTree right;  //     
	int height;  //    
};

using namespace std;
 
int Max(int a,int b)
{
    return a>b?a:b;
}

int Height(AVLTree A)
{
    return A==NULL?-1:A->height;
}

AVLTree RR(AVLTree A)
{
    AVLTree B = A->right;
    A->right =B->left;
    B->left = A;
    A->height = Max(Height(A->left),Height(A->right))+1;
    B->height = Max(Height(B->left),A->height)+1;
    return B;
}

AVLTree LL(AVLTree A)
{
    AVLTree B = A->left;
    A->left = B->right;
    B->right = A;
    A->height = Max(Height(A->left),Height(A->right))+1;
    B->height = Max(Height(B->left),A->height)+1;
    return B;
}

AVLTree LR(AVLTree A)
{
    A->left = RR(A->left);
    return LL(A);
}
 
AVLTree RL(AVLTree A)
{
    A->right = LL(A->right);
    return RR(A);
}

AVLTree Insert(AVLTree T,int x){
	if(!T){  //        ，      
		T = (AVLTree)malloc(sizeof(struct AVLNode));
		T->data = x;
		T->left = NULL;
		T->right = NULL;
		T->height = 0;
	}else{  //      ， 
		if(x < T->data){  //     
			T->left = Insert(T->left,x);
			if(Height(T->left)-Height(T->right)==2){
				if(x < T->left->data) 
					T = LL(T); 
				else if(T->left->data < x)
					T = LR(T); 
			}
		}else if(T->data < x){
			T->right = Insert(T->right,x);
			if(Height(T->right)-Height(T->left)==2){
				if(x < T->right->data)
					T = RL(T); 
				else if(T->right->data < x)
					T = RR(T); 
			}
		}
	}
	//     
	T->height = Max(Height(T->left),Height(T->right)) + 1;
	return T;
} 


int main()
{
    AVLTree T = NULL;
    int n,i;
    cin>>n;
    for(i=0;i<n;i++){
        int temp;
        cin>>temp;
        T = Insert(T,temp);
    }
    cout<<T->data;
    return 0;
}