原题：

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.

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 <sstream>
#include <string>
using namespace std;


template<typename T>class AVLTreeNode;
template<typename T>AVLTreeNode<T>* SingleLeftRotation(AVLTreeNode<T>* A);
template<typename T>AVLTreeNode<T>* SingleRightRotation(AVLTreeNode<T>* A);
template<typename T>AVLTreeNode<T>* DoubleLeftRightRotation(AVLTreeNode<T>* A);
template<typename T>AVLTreeNode<T>* DoubleRightLeftRotation(AVLTreeNode<T>* A);

template<typename T>class AVLTreeNode
{
public:
    T Data;
    AVLTreeNode<T>* Left;
    AVLTreeNode<T>* Right;
    int Height;
};

inline int Max(int a, int b)
{
    return a > b ? a : b;
}

template<typename T>int GetHeight(AVLTreeNode<T>* A)
{
    if(!A)
        return 0;

    return Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
}

template<typename T>AVLTreeNode<T>* AVL_Insertion(T x, AVLTreeNode<T>* t)
{
    if(!t)
    {
        t = new AVLTreeNode<T>;
        t->Data = http://www.mamicode.com/x;>





Root of AVL Tree