1066 Root of AVL Tree (25分)

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 65

Sample Output 2:

88

#include<iostream>
#include<algorithm>

using namespace std;

const int N=30;

int l[N],r[N],v[N],h[N],idx;

void update(int u)
{
    h[u]=max(h[l[u]],h[r[u]])+1;
}

void R(int& u)
{
    int p=l[u];
    l[u]=r[p],r[p]=u;
    update(u),update(p);
    u=p;
}
void L(int& u)
{
    int p=r[u];
    r[u]=l[p],l[p]=u;
    update(u),update(p);
    u=p;
}
int get_balance(int u)
{
    return h[l[u]] - h[r[u]];
}

void insert(int &u,int w)
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }
    else if(w<v[u])
    {
        insert(l[u],w);
        if(get_balance(u)==2)
        {
            if(get_balance(l[u])==1) R(u);
            else L(l[u]),R(u);
        }
    }
    else
    {
        insert(r[u],w);
        if(get_balance(u)==-2)
        {
            if(get_balance(r[u])==-1) L(u);
            else R(r[u]),L(u);
         } 
    }
    update(u);
}
int main()
{
    int n,root=0;
    cin>>n;

    while(n--)
    {
        int w;
        cin>>w;
        insert(root,w);
    }

    cout<<v[root]<<endl;

    return 0;
}