1.题目给出一个数组，要求逐个输入后，输出AVL树的根。
2.这道题比较重要，主要考察AVL树的建立。
3.需要掌握单旋转，双旋转，插入等操作。
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
AC代码：
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
/*
5
88 70 61 96 120
7
88 70 61 96 120 95 65
*/
struct AvlNode{
int val, height;
AvlNode*l, *r;
AvlNode() :val(-1), height(-1), l(NULL), r(NULL){};
AvlNode(int x) :val(x), height(0), l(NULL), r(NULL){};
};
static int Height(AvlNode* T)
{
if (T == NULL) return -1;
else return T->height;
}
static AvlNode* SingleRotateLeft(AvlNode* k2)
{
AvlNode*k1 = k2->l;
k2->l = k1->r;
k1->r = k2;
k2->height = max(Height(k2->l), Height(k2->r)) + 1;
k1->height = max(Height(k1->l), k2->height) + 1;
return k1;
}
static AvlNode* SingleRotateRight(AvlNode* k1)
{
AvlNode*k2 = k1->r;
k1->r = k2->l;
k2->l = k1;
k1->height = max(Height(k1->l), Height(k1->r)) + 1;
k2->height = max(Height(k2->r), k1->height) + 1;
return k2;
}
static AvlNode* DoubleRotateLeft(AvlNode* k3)
{
k3->l = SingleRotateRight(k3->l);
return SingleRotateLeft(k3);
}
static AvlNode* DoubleRotateRight(AvlNode* k3)
{
k3->r = SingleRotateLeft(k3->r);
return SingleRotateRight(k3);
}
static AvlNode* Insert(int x, AvlNode*T)
{
if (T == NULL)
T = new AvlNode(x);
else if (x < T->val)
{
T->l = Insert(x, T->l);
if (Height(T->l) - Height(T->r) == 2)
{
if (x < T->l->val)
T = SingleRotateLeft(T);
else
T = DoubleRotateLeft(T);
}
}
else if (x > T->val)
{
T->r = Insert(x, T->r);
if (Height(T->r) - Height(T->l) == 2)
{
if (x>T->r->val)
T = SingleRotateRight(T);
else
T = DoubleRotateRight(T);
}
}
T->height = max(Height(T->l), Height(T->r)) + 1;
return T;
}
int main(void)
{
int n;
cin >> n;
AvlNode* root = NULL;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
root=Insert(tmp, root);
}
cout << root->val << endl;
return 0;
}
