平衡二叉树（AVL）

AVL 树是带平衡条件的二叉搜索树：任意结点左右子树高度差的绝对值不超过 1。插入或删除后若破坏该条件，通过旋转恢复，从而避免普通 BST 退化成链表。

AVL 得名于发明者 Adelson-Velsky 与 Landis。

本文解决什么问题

• 为何需要平衡
• 平衡因子与四种失衡形态
• 旋转在做什么
• 和红黑树 / std::map 的关系

为什么需要平衡

有序依次插入普通 BST 可能得到斜树，查找退化到 $O(n)$。AVL 将树高维持在 $O(\log n)$，查找、插入、删除（含旋转）均为 $O(\log n)$。

**平衡因子（Balance Factor）**常见定义：

$$bf(v) = height(v.left) - height(v.right)$$

AVL 要求每个结点 $bf \in \{-1, 0, 1\}$。

旋转（直觉）

插入或删除后，自下而上检查；若某结点失衡，按「哪边高、孙子在哪侧」分成四种形态：

形态	含义	处理
LL	左孩子的左侧过高	右旋
RR	右孩子的右侧过高	左旋
LR	左孩子的右侧过高	先左旋再右旋
RL	右孩子的左侧过高	先右旋再左旋

旋转是局部指针调整：

• 保持 BST 中序有序
• 降低局部高度差

右旋示意（LL）:

      y                x
     / \              / \
    x   C    →       A   y
   / \                  / \
  A   B                B   C

插入过程骨架

1. 按 BST 规则插入
2. 沿路径回更新高度 / 平衡因子
3. 若发现失衡，按形态旋转一次（插入引起的失衡，旋转一次即可恢复）
4. 继续向上直到根

删除后的失衡可能沿路径多次旋转，实现更绕。

和红黑树

	AVL	红黑树
平衡严格度	更严（高度差 ≤ 1）	较松（染色约束）
查找	往往略更快（更矮）	略逊一筹但通常够用
插入删除	旋转可能更勤	常更少旋转，工程更偏爱
C++	较少直接暴露	std::map / std::set 常用红黑树

初学用 AVL 理解「平衡 + 旋转」最直观；写工程有序映射优先标准库。

实现建议

完整 AVL 代码较长（高度维护、四种旋转、删除后修复）。建议：

1. 先画图手算 LL/RR/LR/RL
2. 再写只有插入的版本
3. 最后补删除

本篇先把问题与手段讲清；与 BST、堆对照着看选型。

小结

AVL = BST + 高度平衡 + 旋转修复。记住四种失衡与对应旋转，就抓住了核心。下一篇：堆。