In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented.[2] 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. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where $n$ is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Wikipedia

# 定义

$$BF=该节点的左子树高度-该节点的右子树高度$$
AVL树保证每个结点的 BF 满足：
$$\left|BF\right|\le1$$

# 平衡的保持

• LL-rotation 左孩子的左子树
• RR-rotation 右孩子的右子树
• LR-rotation 左孩子的右子树
• RL-rotation 右孩子的左子树

# 复杂度

$$N_H=N_{H-1}+N_{H-2}+1$$

$$F_0=0$$

$$F_1=1$$

$$F_i=F_{i-1}+F_{i-2},(i>1)$$

$$N_H=F_{H+2}-1$$

$$F_i\approx\frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^i$$

$$N_H\approx\frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^{H+2}-1$$

$$h\propto\ln{N_H}$$

$$h=O(\ln{N})$$