AVL Tree

定义

AVL 树（平衡二叉树）是一种自平衡的二叉搜索树，由 Adelson-Velsky 和 Landis 发明。树上任一结点的左子树和右子树的高度差（平衡因子）不超过 1。

平衡因子

$平衡因子 = 左子树高度 - 右子树高度$

取值只能是 -1、0、1。

平衡旋转

插入或删除导致不平衡时，通过旋转恢复平衡：

• LL 旋转（右单旋转）：在左子树的左子树插入导致不平衡
• RR 旋转（左单旋转）：在右子树的右子树插入导致不平衡
• LR 旋转（先左后右双旋转）：在左子树的右子树插入导致不平衡
• RL 旋转（先右后左双旋转）：在右子树的左子树插入导致不平衡

性能

• 查找、插入、删除：$O(\log_2 n)$
• n 个结点的 AVL 树的最大深度约为 $1.44 \log_2(n+2) - 0.328$