An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120结尾无空行
Sample Output 1:
70结尾无空行
Sample Input 2:
7
88 70 61 96 120 90 65Sample Output 2:
88这题主要要弄清楚LL旋转、RR旋转、LR旋转、RL旋转分别是怎么操作，怎么用代码表示：
1、可以看出来，RR旋转是将B的左树连到A的右边，然后B的左树变为A即可，代码为：
Tree single_right_rotation(Tree A)
{
Tree 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;
}
2、LL旋转是将B的右子树连到A的左边，B的右子树变为A。代码表示为：
Tree single_left_rotation(Tree A)
{
Tree 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;
}
3、LR旋转看着不太明显，其实可以看成先将B--C这段进行右单旋（图中红色框住的部分），也就是C连上了A，然后B在C的左边；随后，对C----A这段进行左单旋，将C放在了最上面，A在C的右侧。代码实现为：
Tree left_right_rotation(Tree A)
{
A->left=single_right_rotation(A->left);
return single_left_rotation(A);
}
4、RL旋转同理，红色线框中的部分是不是和左单旋非常像。所以先对这部分做左单旋，然后对A----C部分做右单旋。代码实现为：
Tree right_left_rotation(Tree A)
{
A->right=single_left_rotation(A->right);
return single_right_rotation(A);
}
弄明白了核心原理，接下来就是输出代码了：
这其中有关于左右子树高度的判断代码GetHeight，毕竟想要得到平衡二叉树，首先得知道什么时候不平衡
//04-树5 Root of AVL Tree
#include<stdio.h>
#include<stdlib.h>struct AVLtree_Node{
int number;
struct AVLtree_Node* left;
struct AVLtree_Node* right;
int height;
};typedef struct AVLtree_Node* Tree;
int Max(int a, int b);
int GetHeight(Tree T);
Tree single_left_rotation(Tree A);
Tree single_right_rotation(Tree A);
Tree left_right_rotation(Tree A);
Tree right_left_rotation(Tree A);
Tree NewNode(int Data);
Tree Insert(Tree T, int Data);int main()
{
int N=0, i=0, Data=0;
scanf("%d", &N);
if(N){
scanf("%d", &Data);
Tree T= NewNode(Data);
for(i=1;i<N;i++){
scanf("%d", &Data);
T = Insert(T,Data);
}
printf("%d", T->number);
}
return 0;
}int Max(int a, int b)
{
return a>b?a:b;
}int GetHeight(Tree T) //关于左右子树高度的判断
{
int Hl, Hr, MaxH;
if(T){
Hl=GetHeight(T->left);
Hr=GetHeight(T->right);
MaxH = Max (Hl, Hr);
return MaxH+1;
}
else return 0;
}Tree single_left_rotation(Tree A)
{
Tree 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;
}Tree single_right_rotation(Tree A)
{
Tree 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;
}Tree left_right_rotation(Tree A)
{
A->left=single_right_rotation(A->left);
return single_left_rotation(A);
}Tree right_left_rotation(Tree A)
{
A->right=single_left_rotation(A->right);
return single_right_rotation(A);
}Tree NewNode(int Data)
{
Tree T = (Tree) malloc (sizeof(struct AVLtree_Node)) ;
T->height=0;
T->left=T->right=NULL;
T->number=Data;
return T;
}Tree Insert(Tree T, int Data)
{
if(!T) T = NewNode(Data);
else{
if(Data>T->number) {
T->right=Insert(T->right, Data);
if(GetHeight(T->right)-GetHeight(T->left)==2){
if(Data > T->right->number) T=single_right_rotation(T);
else T=right_left_rotation(T);
}
}
else{
T->left=Insert(T->left, Data);
if(GetHeight(T->right)-GetHeight(T->left)==-2){ //平不平衡的判断
if(Data < T->left->number) T=single_left_rotation(T);
else T=left_right_rotation(T);
}
}
}
T->height = Max(GetHeight(T->left), GetHeight(T->right))+1;
return T;
}