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
AVL树的旋转。
#include <bits/stdc++.h>
using namespace std; const int maxn = 101000;
struct Node {
int val;
int son[2];
int height;
}s[maxn];
int root, sz;
int n; int add(int x) {
s[sz].val = x;
s[sz].son[0] = s[sz].son[1] = -1;
s[sz].height = 0;
sz ++;
return sz - 1;
} int Height(int id) {
if(id == -1) return -1;
return s[id].height;
} int R(int k2) {
int k1 = s[k2].son[0];
s[k2].son[0] = s[k1].son[1];
s[k1].son[1] = k2;
s[k2].height = max(Height(s[k2].son[0]), Height(s[k2].son[1])) + 1;
s[k1].height = max(Height(s[k1].son[0]), Height(s[k1].son[1])) + 1;
return k1;
} int L(int k2) {
int k1 = s[k2].son[1];
s[k2].son[1] = s[k1].son[0];
s[k1].son[0] = k2;
s[k2].height = max(Height(s[k2].son[0]), Height(s[k2].son[1])) + 1;
s[k1].height = max(Height(s[k1].son[0]), Height(s[k1].son[1])) + 1;
return k1;
} int RL(int k3) {
int k1 = s[k3].son[1];
s[k3].son[1] = R(k1);
return L(k3);
} int LR(int k3) {
int k1 = s[k3].son[0];
s[k3].son[0] = L(k1);
return R(k3);
} int Insert(int id, int val) {
if(id == -1) {
id = add(val);
} else if(val < s[id].val) {
s[id].son[0] = Insert(s[id].son[0], val);
if(Height(s[id].son[0]) - Height(s[id].son[1]) == 2) { // 需要调整
if(val < s[s[id].son[0]].val) id = R(id);
else id = LR(id);
}
} else {
s[id].son[1] = Insert(s[id].son[1], val);
if(Height(s[id].son[1]) - Height(s[id].son[0]) == 2) { // 需要调整
if(val > s[s[id].son[1]].val) id = L(id);
else id = RL(id);
}
}
s[id].height = max(Height(s[id].son[0]), Height(s[id].son[1])) + 1;
return id;
} int main() {
scanf("%d", &n);
root = -1;
for(int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
root = Insert(root, x);
// cout << root << endl;
}
cout << s[root].val << endl;
return 0;
}