平衡二叉树的根

7-29 平衡二叉树的根 （25 分）

将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入格式:

输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。
输出格式:

在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
输入样例1:

5
88 70 61 96 120

输出样例1:

70

输入样例2:

7
88 70 61 96 120 90 65

输出样例2:

88

#include<cstdio>
#include<algorithm> 
using namespace std;
typedef struct node* AVL;
struct node{
	int data;
	AVL left;
	AVL right;
	int height;//树高 
};
int getheight(AVL T){  //获取树高 
	if(!T){//没有这句会炸o(╥﹏╥)o
		return 0;
	} 
	return T->height;
}
AVL sl(AVL A){  //左单旋 
	//A必须有一个左子结点B
	AVL B=A->left;
	A->left=B->right;
	B->right=A;
	A->height=max(getheight(A->left),getheight(A->right))+1;
	B->height=max(getheight(B->left),getheight(B->right))+1;
	return B; 
} 
AVL sr(AVL A){  //右单旋 
	//A必须有一个右子结点B
	AVL B=A->right;
	A->right=B->left;
	B->left=A;
	A->height=max(getheight(A->left),getheight(A->right))+1;
	B->height=max(getheight(B->left),getheight(B->right))+1;
	return B;
}
AVL dlr(AVL A){ //左右双旋 
	//A必须有一个左子结点B，且B必须有一个右子结点C
	A->left=sr(A->left);//将B与C做右单旋，C被返回
	return sl(A);//将A与C做左单旋，C被返回 
}
AVL drl(AVL A){ //右左双旋 
	//A必须有一个右子结点B，且B必须有一个左子结点C
	A->right=sl(A->right);//将B与C做左单旋，C被返回
	return sr(A);//将A与C做右单旋，C被返回 
}
AVL insert(AVL T,int X){//AVL树的插入操作 
	if(!T){//若插入空树，则新建包含一个结点的书 
       T=new node;
       T->data=X;
       T->height=1;
       T->left=T->right=NULL;
       //return T;
	}
	else if(X<T->data){  //插入T的左子树 
		T->left=insert(T->left,X);
		//如果需要左旋 
		if(getheight(T->left)-getheight(T->right)==2){
		   if(X<T->left->data) 
		   T=sl(T);//左单旋
		   else
		   T=dlr(T);//左右双旋 
	    }
	}
	else if(X>T->data){//插入T的右子树
	    T->right=insert(T->right,X);
		//如果需要右旋
		if(getheight(T->left)-getheight(T->right)==-2){
			if(X>T->right->data)
			T=sr(T);//右单旋 
			else
			T=drl(T);//右左双旋 
		} 	
	} 
	//else X==T->data无需插入
	
	T->height=max(getheight(T->left),getheight(T->right))+1;//更新树高 
	return T; 
}
int main(){
	AVL T=NULL;	
	int n,x;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		T=insert(T,x);
	}
	printf("%d\n",T->data);
	return 0;
}