1066 Root of AVL Tree
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 • 1 • 2
Sample Output 1:
70
Sample Input 2:
7 88 70 61 96 120 90 65 • 1 • 2
Sample Output 2:
88
题意
给定一个序列，让我们构建起一颗 AVL 树，并输出它的根结点。
思路
平衡二叉树失衡主要分为四种情况，下面讨论的是导致失衡前最后插入的一个结点位置：
插入的结点在失衡结点的左孩子的左子树，直接右旋失衡结点。
插入的结点在失衡结点的左孩子的右子树，先对失衡结点的左孩子进行左旋，再对失衡结点右旋。
插入的结点在失衡结点的右孩子的右子树，直接左旋失衡结点。
插入的结点在失衡结点的右孩子的左子树，先对失衡结点的右孩子进行右旋，再对失衡结点左旋。
代码
#include<bits/stdc++.h> using namespace std; const int N = 25; int l[N], r[N], v[N], h[N], idx; int n; //更新当前结点的深度 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() { cin >> n; int root = 0; for (int i = 0; i < n; i++) { int w; cin >> w; insert(root, w); } cout << v[root] << endl; return 0; }
