AVL 树

对于二叉树中的任何一个节点 \(v\)，它的平衡因子就是它的左子树高度与右子树高度之差，即：

\(balFac(v)=height(lc(v)) - height(rc(v))\)

所谓 AVL 树就是其中所有节点的平衡因子都不超过 1 也不小于 -1，即：

\(\forall v,|balFac(v)|\leq 1\)

增加

增加算法稍微简单，无非就是单旋或双旋两种情况而已。

其重平衡的时间复杂度为 \(O(1)\)。

删除

因有失衡传播现象，可能需做 \(O(logn)\) 次调整。