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 ythe root of the resulting AVL tree in one line.

588 70 61 96 120Sample Output 1:
70Sample Input 2:
788 70 61 96 120 90 65Sample Output 2:
88
注意：
開始時要初始化，將root結點的height設成0，否則段錯誤。
要注意左旋和右旋的寫法。
#include <stdio.h>#include <stdlib.h>#include <iostream>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <stack> #include <queue>using namespace std;const int maxn=110; int n,m,s;struct node{ node *left; node *right; int  v,height;//高度可理解為以該節點為根的樹的層數 }*root,*null; void init(){    null=new node;    null->height=0;    root=null;//null為 高度為0 }node* newNode(int v)//設置新的節點 {     node* t=new node();     t->v=v;     t->height=1;    t->left=t->right=null;     return t; } void getNewheight(node *root){    root->height=max(root->left->height,root->right->height)+1;}void L(node *&root){    node *tmp=root->right;    root->right=tmp->left;    tmp->left=root;    getNewheight(root);    getNewheight(tmp);    root=tmp;    }void R(node *&root){    node* tmp=root->left;    root->left=tmp->right;    tmp->right=root;    getNewheight(root);    getNewheight(tmp);    root=tmp;}void insert(node *&root,int v){    if(root==null)    {     root=newNode(v);     return;        }     if(v<root->v)    {        insert(root->left,v);        getNewheight(root);        if((root->left->height)-(root->right->height)==2)        {            //ll型             if((root->left->left->height)-(root->left->right->height)==1)            {                R(root);             }else if((root->left->left->height)-(root->left->right->height)==-1)            {                //lr                L(root->left);                R(root);            }        }    }else    {        insert(root->right,v);        getNewheight(root);        if((root->left->height)-(root->right->height)==-2)        {            if((root->right->left->height)-(root->right->right->height)==1)            {//rl                R(root->right);                L(root);            }else if((root->right->left->height)-(root->right->right->height)==-1)            {	//rr                L(root);            }        }    }}int main(){    int n,v;    init();    scanf("%d",&n);    for(int i=0;i<n;i++)    {        scanf("%d",&v);        insert(root,v);    }    printf("%d/n",root->v);    return 0;}