平衡二叉树（AVL 树）

平衡二叉树（AVL 树）是一种特殊的二叉排序树，由 Adelson-Velsky 和 Landis 提出。它的核心约束是：对树中每一个结点，其左子树高度与右子树高度之差的绝对值不超过 1。

平衡因子（Balance Factor）

定义结点 $v$ 的平衡因子 BF(v) = h_L(v) − h_R(v)，其中 $h_L, h_R$ 分别为左右子树高度。AVL 树要求对所有结点 $|BF(v)| \le 1$。

失衡的四种类型

类型	触发形状	旋转操作
LL	BF=+2，且左孩子的 BF ≥ 0	对失衡结点右单旋
RR	BF=−2，且右孩子的 BF ≤ 0	对失衡结点左单旋
LR	BF=+2，且左孩子的 BF < 0	先左后右双旋
RL	BF=−2，且右孩子的 BF > 0	先右后左双旋

LL（右单旋）

失衡结点 A 的左子树更高，且左孩子 B 的左子树更高（A−B−C 一条左链）。将 B 提为根，A 降为 B 的右孩子，原 B 的右子树变为 A 的左子树。

RR（左单旋）

失衡结点 A 的右子树更高，且右孩子 B 的右子树更高（A−B−C 右链）。将 B 提为根，A 降为 B 的左孩子。

LR（先左后右双旋）

失衡 A 的左孩子 B 的右子树更高（插入到 B 的右子树）。先对 B 左单旋，再对 A 右单旋。

RL（先右后左双旋）

失衡 A 的右孩子 B 的左子树更高。先对 B 右单旋，再对 A 左单旋。

依次插入 3, 2, 1, 4, 5, 6, 7，观察旋转如何维持平衡：

• 插入 3, 2：正常，无失衡。
• 插入 1：在 3 的左孩子 2 的左，形成 LL，对 3 右单旋 → 根为 2（左 1 右 3）。
• 插入 4：挂在 3 的右，正常。
• 插入 5：在 3 的右、4 的右，形成 RR，对 3 左单旋 → 根为 4（左 3 右 5）。
• 插入 6：在 4 的右、5 的右，RR，对 4 左单旋 → 根为 5（左 4 右 6）。此时全局根为 2，右子树为 5。
• 插入 7：在 5 的右、6 的右，RR，对 5 左单旋 → 根为 6（左 5 右 7）。

最终 AVL 树：