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:
588 70 61 96 120
Sample Output 1:
70
Sample Input 2:
788 70 61 96 120 90 65
Sample Output 2:
88
AVL树的旋转。
#includeusing 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;}