一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

最少节点数

在高度为h的AVL树中，最少节点数S(h)=S(h-1)+S(h-2)+1,对于h=1，S(h)=1；h=1，S(h)=2。

插入之后重平衡

插入一个节点可能破坏AVL树的特性。此时需要对树进行简单的修正来重新恢复AVL树的平衡。
这些修正通常都是对失去平衡的节点进行旋转(rotation)。

如果把失去平衡的节点看作a，那么不平衡的情况就只能是下面四种情况：

  1. 对a的左儿子的左子树进行一次插入。
  2. 对a的左儿子的右子树进行一次插入。
  3. 对a的右儿子的左子树进行一次插入。
  4. 对a的右儿子的右子树进行一次插入。

1和4是关于a点的镜像对称，2和3也是关联a点的镜像对称。所以理论上是只有两种情况，也就是说，1和4这两种情况的处理只需要做反方向处理即可。

1和4这种情况只需要通过对树进行一次单旋转即可完成重新平衡。
2和3这种情况需要通过双旋转来处理。