Scott's world.

# Root of AVL Tree

Word count: 1.1kReading time: 5 min
2019/07/26 Share

# 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 Ndistinct 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.

## 题目分析

AVL树即平衡二叉搜索树, 在AVL树中，任何节点的两个子子树的高度最多相差一个

1. 对a的左儿子的左子树进行一次插入。（左-左） LL
2. 对a的左儿子的右子树进行一次插入。（左-右） LR
3. 对a的右儿子的左子树进行一次插入。（右-左） RL
4. 对a的右儿子的右子树进行一次插入。（右-右） RR

• 单旋转—情形1和4：

• 双旋转—情形2和3：

情形2和3就是向上图中的子树Y插入一个节点，由上图可知，无论是左单旋还是右单旋都无法改变子树Y的高度。解决办法是再将子树Y分解成根节点和相应的左子树和右子树，然后对相应的节点做相应的旋转，如下图：