自平衡树：AVL 与红黑树

03-树与堆进阶预计 25 分钟平衡树AVL红黑树旋转

学习状态：

一句话定义

自平衡二叉搜索树在插入/删除后通过旋转（Rotation）与重新着色把树高维持在 O(log n)：AVL 树用「任意节点左右子树高度差 ≤ 1」的强平衡；红黑树用一组红黑性质保证最长路径不超过最短路径两倍，换取更少的更新期调整。

为什么重要

BST 的退化问题在真实数据（近乎有序的插入流）中几乎必然发生，平衡树是有序映射 ADT 在内存中的默认答案：C++ std::map、Java TreeMap、Linux 内核 CFS 调度器都是红黑树。掌握「旋转保序」这一机制，就掌握了从 BST 推广到一切自平衡结构（含 B 树、treap、splay）的通用武器。

前置知识

kp-012（BST 性质与删除）；kp-002（O(log n) 的含义）。

核心概念

旋转：在不破坏 BST 序的前提下改变局部高度的重挂操作；左旋/右旋互为逆操作，是所有平衡树的原子动作。
AVL：平衡因子 bf = 右高 − 左高 ∈ {−1,0,1}；插入后回溯修复，失衡四型 LL/RR/LR/RL 分别用单旋或「先旋孩子再旋自己」的双旋解决；查找极优，更新调整最多 O(log n) 次旋转。
红黑树五性质：节点红或黑；根黑；叶哨兵（NIL）黑；红节点孩子必黑（无红红）；任一节点到其所有叶子的黑高相等。由性质可证高度 ≤ 2·log₂(n+1)。
红黑树更新：插入默认染红，按「叔叔颜色」分情形重着色/旋转；删除情形更多（工程上普遍「用库不自虐」）。
选型直觉：查询密集选 AVL（更矮）；更新频繁选红黑（调整更少）；两者操作都稳定 O(log n)。

直观类比

AVL 是「强迫症图书管理员」：每放一本书都立即把整架重新码到近乎完美对称，找书极快，但每放一本都折腾；红黑树是「务实管理员」：允许书架有轻微歪斜（红节点），只在实在不像话时才整理一次，放书轻松、找书也不差。

原理与机制

右旋的保序证明（左旋对称）：对节点 y 及其左孩子 x 旋转后，子树 keys 的相对顺序（α < x < β < y < γ）不变，仅父子关系重排——这正是不变量思维的价值：旋转只需要证序不变，高度变化交给 AVL 的 bf 或红黑的性质去追。

右旋（以 x 为轴）:            左旋（以 y 为轴）:
    y                x            x                  y
   / \              / \          / \               / \
  x   γ    ⇒       α   y        α   y      ⇒      x   γ
 / \                  / \          / \            / \
α   β                β   γ        β   γ          α   β

高度界直觉：黑高相等 ⇒ 树至少含 2^(bh−1) − 1 个内部节点（黑高 bh）；红红不相邻 ⇒ 每条路径至多一半是红 ⇒ h ≤ 2·bh ⇒ n ≥ 2^(h/2) − 1 ⇒ h ≤ 2·log₂(n+1)。

图示

AVL 失衡四型（插入后回溯到 z 为首个失衡点）:
LL: 左孩左插  → 右旋 z
RR: 右孩右插  → 左旋 z
LR: 左孩右插  → 先左旋孩子, 再右旋 z
RL: 右孩左插  → 先右旋孩子, 再左旋 z
例（RR）:  1                2
             \            / \
              2    ⇒    1   3
               \
                3

实例或案例

C++ std::map/set/multimap、Java TreeMap/TreeSet：有序遍历、范围查询、前驱后继全是 O(log n)。
Linux 完全公平调度器（CFS）用红黑树按虚拟运行时间组织可运行任务，取最左节点即最该上 CPU 的任务。
AVL 的典型用场：读多写少的索引表（如编译器符号表）。

常见误区

把红黑树当「完全平衡」：它只保证两倍界，实际高度可能明显大于 ⌈log n⌉；AVL 才是严格近似平衡。
死背旋转模板不证序不变量：换一个结构（B 树、treap）就失效；旋转的正确性只有一个来源——序不变。
生产代码手写红黑树：插入/删除情形组合极易写错，工程上应使用标准库，理解原理即可。
以为 AVL 永远优于 BST：在小数据或随机插入下，简单 BST/哈希的常数可能更划算，平衡树解决的是「最坏保证」。

自测题

依次插入 1..7 到 AVL，最终树的形状与根是什么？

答案要点：根 4，形如 4(2(1,3),6(5,7))——完美平衡；中途经历 RR/LL 修复。

证明红黑树高度 ≤ 2·log₂(n+1) 的关键两步是什么？

答案要点：①黑高相等 ⇒ 子树规模随黑高指数下界 n ≥ 2^bh − 1；②红红不相邻 ⇒ bh ≥ h/2；联立即得。

插入导致「红红冲突」且叔叔为红时，处理动作是什么？为什么可能向上传播？

答案要点：父与叔染黑、祖父染红，冲突上移到祖父；因为祖父变红可能与曾祖父再成红红。

与其他知识点的关系

kp-012 是其退化基线；旋转思想在 kp-015 的 B 树分裂合并中同源；kp-014 堆与之对照——堆牺牲「全序」换「部分序」，换得更简单的更新；kp-030 并查集则展示另一种「不追求完全平衡」的近 O(1) 思路。

延伸阅读

《算法导论》第 13 章（红黑树全推导）；Sedgewick《算法（第 4 版）》左倾红黑树（LLRB）一节，实现比经典版简洁得多。

前置知识点

二叉搜索树：性质、查找与删除核心