平衡树是在二叉搜索树的基础上,通过维护结构不变量把树高限制在对数级的存储结构。本文讨论 AVL 树与红黑树的原理、实现与工程落点。二叉搜索树的性质与退化问题是本篇的出发点,有序数组与链式存储在查找与更新代价上的互补见 数组与链表;有序映射这一类抽象数据类型在 ADT 体系中的位置见 抽象数据类型(ADT);树高与复杂度的分析口径见 复杂度与算法分析;用随机层数替代旋转的另一条路线见 跳表;工程中红黑树的实际落点见 Java 集合框架实现原理;哈希冲突被树化兜底的方式见 散列表。

一、起源:二叉搜索树的退化代价

1. 两种极端结构的互补

按键查找与更新的代价,取决于数据在内存中的组织方式。两种最基础的有序结构正好互补:

结构 按值查找 插入 删除 有序遍历
有序数组 二分 O(log n) 搬移元素 O(n) 搬移元素 O(n) O(n),顺序访问
有序链表 顺序扫描 O(n) 已定位后 O(1) 已定位后 O(1) O(n),顺序访问

有序数组的查找是 O(log n),代价是每次更新都要搬移元素,为 O(n);链表的更新只改指针,但定位必须顺序扫描,同样为 O(n)。两者的取舍方向相反,且都是"查找快则更新慢"或"更新快则查找慢"。

两种结构都无法同时把查找与更新压到对数级,原因是它们的有序性由"物理位置"直接表达:数组靠下标顺序,链表靠指针顺序。要同时获得对数级查找与对数级更新,需要在存储中引入一层"索引形状"上的信息,让结构本身能够记录元素的相对次序,而不依赖元素的物理位置连续或链式相邻。

关于两种存储方式的内存布局、缓存行为与真实代价,见 数组与链表 的复杂度对照与选型部分。

2. 二叉搜索树的期望与最坏

二叉搜索树(Binary Search Tree,BST)给出了另一种表达次序的方式:每个节点的键大于左子树中所有键、小于右子树中所有键。由此,查找沿一条从根向下的路径进行,每比较一次下降一层(该结构的有序性、查找插入删除与前驱后继的完整实现见 二叉树与二叉搜索树):

查找 key:
    从根开始
    若 key 等于当前节点的键,命中
    若 key 小于当前节点的键,进入左子树
    若 key 大于当前节点的键,进入右子树
    走到空指针,说明 key 不存在

查找的比较次数等于路径长度,也就是树高。插入与删除同样是"先沿路径定位,再改动少量指针",代价也是树高。

若键的插入顺序是随机的,树在期望意义上是"大致平衡"的:n 个节点的期望树高为 O(log n),因此插入、删除、查找都是期望 O(log n)。但这一结论依赖"随机插入顺序"这一前提。

3. 退化的代价

前提被破坏时,BST 会退化成一条链。按键的升序依次插入 1 至 n:

按 1, 2, 3, 4, 5 升序插入

     1                 1
      \                 \
       2                 2
        \                 \
         3        ⇒         3
          \                 \
           4                 4
            \                 \
             5                 5

平衡形态(高度 5)          退化形态(高度 5,但形状是一条链)

上例中两侧节点数相同,形状却是"尽量扁"与"完全成链"的差别。退化后树高为 n,查找、插入、删除全部退化为 O(n),与顺序扫描有序链表没有区别,但每个节点还多付出了两个指针的空间代价——结构变差了,代价却更高。

退化并非罕见输入造成的意外。以下都属常见来源:

  1. 键本身有序。按时间递增的日志、自增主键、按文件路径排序的目录项,读入顺序天然有序。
  2. 批量导入。从数据库按主键顺序 ORDER BY 取出一批记录再逐条插入,顺序已定。
  3. 外部可控的输入。键来自请求参数或用户上传的数据时,攻击者可以构造出让结构退化的插入顺序,这与散列表被恶意构造哈希碰撞属于同一类问题(见 散列表 的哈希攻击一节)。

结果是:BST 的性能没有保证,只有期望。在延迟上界需要被推导或承诺的场景中,"期望 O(log n)"不足以作为依据——这与跳表的处境相同,区别在于跳表的退化概率随元素数指数下降且与输入无关,BST 的退化可以由输入直接触发。

4. 维护结构不变量

要把树高压在对数级,需要让结构在每次更新后主动维持某种形状约束。可用的手段是在不改变键序的前提下做局部重塑:

旋转(rotation) 是这一手段的基本操作。它以相邻的两个节点为轴交换父子关系,参与的两个节点在键序上本来就是父子,交换后所有键的相对顺序不变。以右旋为例:

        y                       x
       / \                     / \
      x   T3      ──右旋──►   T1  y
     / \                         / \
    T1  T2                      T2  T3

中序序列:T1  x  T2  y  T3    →    T1  x  T2  y  T3      完全不变

旋转前后中序遍历的结果完全相同,这是因为旋转只改变了x与y的父子指向,没有跨越任何键的相对次序。这一点决定了基于旋转的平衡方案是可行的:可以在任意位置施加任意次数的旋转,而不必重新排序或重建结构。

平衡的含义由此可以精确表述为:在键序不变的前提下,通过旋转等方法让"任意两个叶子的深度差"或"根到各叶子的路径长度"受某个上界约束。约束越紧,树高越小,查找越快;但更新时需要更多次旋转来维持约束,更新越慢。

5. 严格平衡与近似平衡

按照约束的松紧,可以把平衡结构排成一条谱系。

结构 高度不变量的形式 高度上界(n 为节点数) 更新时的调整量
完全平衡(理想) 任意节点左右子树节点数差不超过 1 约 log₂n 维护代价过高,无法在 O(log n) 内更新
AVL 树 任意节点左右子树高度差不超过 1 约 1.44 log₂n 插入最多一次重构;删除可能沿路径级联旋转
红黑树 由五条颜色性质间接约束,最长路径不超过最短路径的两倍 约 2 log₂n 插入与删除的旋转次数为常数,变色可能沿路径传播
跳表 无确定性约束,层数由随机数决定 期望 log n,最坏 n 每层改两个指针,无旋转

完全平衡(任意左右子树节点数差不超过 1)虽然树高最小,但一次插入可能改变大量节点的"节点数差",恢复代价无法控制在对数级,因此不作为动态结构使用,只在静态数据上通过一次性构造实现(如有序数组直接折半建树)。

实际采用的是近似平衡:容忍一定程度的高度不平衡,换取更新路径上的调整量可控。AVL 与红黑树是两种代表性的取舍:

  • AVL 树把约束加在高度差上,约束直观、易于证明,代价是删除时可能沿路径多次旋转。
  • 红黑树把约束加在颜色上,约束不直观,但把旋转次数压到了常数次,更适合更新频繁的场景。

为什么放宽约束能减少调整次数,以及两种约束各自如何导出树高上界,是下一节的内容。需要先明确的是:平衡树的全部设计都围绕"树高上界"与"更新调整量"这对矛盾展开,AVL 与红黑树的差别正是这对矛盾上两个不同的取值点。


二、原理

1. 树高与操作代价

1.1 树高决定一切

平衡树的四类核心操作都可以归结为"沿一条从根到叶的路径走一遍":

操作 代价 理由
查找 O(h) 沿单条路径下降,比较次数不超过 h
插入 O(h) 先定位到空指针,再改动常数个指针
删除 O(h) 先定位到目标,再改动常数个指针
求最值 O(h) 沿最左或最右路径
前驱、后继、取整 O(h) 沿路径下行的同时记录候选,必要时向上回溯一步
中序有序遍历 O(n) 每个节点访问一次,与树高无关

其中 h 表示树高。因此平衡树的全部工作就是给 h 一个上界,把这个上界压得越低,四类操作的比较次数越少。

本文约定:树高指根到最远叶子的路径上的节点数,空树高度为 0,只有根节点的树高度为 1。相应地,"叶子"指没有孩子的节点。若改用边数口径,下文的数值全部减 1,结论的量级不变。

1.2 最少节点数与最大高度

给定节点数 n,树高的最小值与最大值都可以精确计算,两者的差距就是平衡约束的作用范围。

最小值由完全二叉树给出:高度为 h 的二叉树最多容纳 2^h − 1 个节点,因此 n 个节点的二叉树高度不小于 ⌈log₂(n + 1)⌉。这个下界与平衡策略无关,是所有二叉树共同的极限。

AVL 树的最大高度由"节点数最少的高度为 h 的 AVL 树"决定。设 N(h) 为高度为 h 的 AVL 树所含的最少节点数。要构造节点数最少的高度 h 的树,根的两棵子树高度必须尽量极端——一株高度为 h − 1,另一株为 h − 2,且两株各自也是同高度下节点数最少的 AVL 树(高度差不超过 1 的约束使得 h − 2 是允许的最小值)。因此

N(0) = 0                                       空树
N(1) = 1                                       单节点
N(h) = N(h − 1) + N(h − 2) + 1                 h ≥ 2

这一递推与斐波那契数列同形。前若干项为:

h 1 2 3 4 5 6 7 8 9 10
N(h) 最少节点数 1 2 4 7 12 20 33 54 88 143
2^h − 1 最多节点数 1 3 7 15 31 63 127 255 511 1023

解递推可得 N(h) = F(h + 2) − 1,其中 F 为斐波那契数列(F(0) = 0,F(1) = 1)。代入 F(h) ≈ φ^h / √5(φ = (1 + √5) / 2 ≈ 1.618)并对 h 求解:

n ≥ N(h) ≈ φ^(h+2) / √5 − 1
⇒ h ≤ log_φ(√5 · (n + 1)) − 2
⇒ h ≤ 1.44 · log₂(n + 1) − 0.33

即 AVL 树的树高上界约为 1.44 log₂n,是理想下界 log₂n 的 1.44 倍。取 n = 10⁶:

理想下界(完全二叉树)   ⌈log₂(10⁶ + 1)⌉ = 20
AVL 树上界               1.44 × log₂(10⁶ + 1) − 0.33 ≈ 28.4 → 28
实际最大值(据 N(h))    N(27) = F(29) − 1 = 514229 ≤ 10⁶ < N(28) = 1346268 → 27

表中"实际最大值"由最少节点数直接查出:n = 10⁶ 时最坏形状的高度为 28(层数口径),公式给出的 28.4 是它的上界估计。斐波那契式的递推使最坏形状呈"每层只差一层"的瘦长形态,但层数仍是对数级。

红黑树的最大高度由颜色性质导出。设从某个节点出发(不含该节点)到任一叶子的路径上的黑节点数为该节点的黑高,记为 bh。性质 5 保证同一节点的所有下行路径黑高相同。于是有两条结论:

  1. 最短路径长度等于黑高。全由黑节点构成的路径是最短的,其长度为 bh(此处长度按节点数计,含叶子)。
  2. 最长路径长度不超过两倍黑高。性质 4 禁止连续红节点,因此任一路径上红节点数不超过黑节点数,路径长度不超过 2·bh。

因此最长路径不超过最短路径的两倍。再结合节点数的下界:黑高为 bh 的树,其黑节点构成一棵高度为 bh 的"满"结构,内部节点数至少为 2^bh − 1,于是

n ≥ 2^bh − 1  ⇒  bh ≤ log₂(n + 1)
h ≤ 2·bh ≤ 2·log₂(n + 1)

即 红黑树的树高上界约为 2 log₂n。取 n = 10⁶ 时上界约为 40 层,比 AVL 的 28 层宽松约 40%。这一差距直接体现为查找时更多的比较次数,也是红黑树在查找上略逊于 AVL 的原因。

两种树的高度上界与理想下界的关系可以并列看:

              下界        AVL 上界             红黑树上界
高度(层)    log₂n       1.44 log₂n           2 log₂n
n = 10⁶       20          28                    40

1.3 平衡因子与高度的维护

判读"某节点是否失衡"需要知道它左右子树的高度。实现上有两种做法。

做法一:在每个节点保存子树高度。 节点多一个整数字段。判断是否失衡时现算左右子树高度之差,即平衡因子:

bf(node) = height(node.left) − height(node.right)

优点是高度值可以逐层复用,不依赖平衡因子之间的连锁修正;缺点是字段宽度较大(通常 4 字节,也有实现压到 2 字节或 1 字节),且在旋转后需要重算两个节点的高度。

做法二:在每个节点只保存平衡因子。 取值范围是 {−1, 0, +1},两个二进制位即可表示。内存开销最小,但插入与删除后平衡因子的更新依赖对兄弟子树的推断,公式分支多、易错。删除时尤其明显:某节点的平衡因子变化后,其祖先的平衡因子是否变化取决于该子树的高度是否改变,判断链条比做法一长。

两种做法的对照:

维度 保存高度 保存平衡因子
每个节点的额外开销 1 个整数字段(可由 1 字节承载) 2 个二进制位
是否失衡的判断 直接相减 直接读取
旋转后的更新 重算两个节点的高度,公式统一 按旋转类型分别填写,公式多
删除时的回溯判断 比较旋转前后的高度是否变化 依赖平衡因子的连锁修正
出错概率 较低 较高

工程实现与教学实现通常采用做法一:多出的几个字节换取"高度字段可以直接与重算值比对"这一可校验性。红黑树则不需要高度或平衡因子,只用一个颜色位。

1.4 树高之外的成本

树高决定比较次数,但操作的实际耗时还取决于另外两项,二者都不由树高决定:

  1. 每层下降对应一次指针跳转与一次缓存访问。节点在堆上离散分配,树越高,跳转次数越多,缓存未命中的概率越大。这一项的系数与节点大小、分配器的排布有关,与树高同阶但难以解析计算。
  2. 每次比较的代价。整数键的比较是一条指令,字符串键的比较是一次可能跨越多个缓存行的内存扫描。键的比较代价高时,树高从 28 降到 20 带来的收益会被比较本身的开销抵消。

因此树高上界的差别只是查找代价差别的一个来源,具体数值需要实测确定(见第三章第 3 节与 JMH 微基准测试)。

2. AVL 树

AVL 树是最早被提出的自平衡二叉搜索树(1962 年,Adelson-Velsky 与 Landis)。它的平衡条件直接加在高度上,因此约束最直观,也是理解旋转机制最自然的入口。

2.1 平衡因子与不变量

AVL 树的不变量只有一条:

对树中每个节点,其左右子树的高度差的绝对值不超过 1。

利用上节的树高定义(空树高度为 0),可以等价地表述为平衡因子的取值范围:

bf(node) = height(node.left) − height(node.right) ∈ {−1, 0, +1}

bf 为 0 表示两侧等高(平衡),为 +1 表示左高(左重),为 −1 表示右高(右重)。bf 为 +2 或 −2 时节点失衡,需要旋转修复。

由 1.2 节的推导,这一条局部约束足以把整棵树的高度压到 1.44 log₂n 以内,原因是"每个节点两侧高度差不超过 1"迫使子树节点数按斐波那契式增长——形状越瘦长,所需节点越多。

有一条容易忽略的推论:AVL 树的平衡条件是局部且可加性的,每个节点独立判读自己的 bf,不需要知道整棵树的形状。这使得插入与删除都只需沿路径回溯,逐个节点检查,不需要全局重建。

2.2 四种失衡形态

插入或删除后,失衡节点最多只有 bf = ±2 两种取值(一次操作最多使某侧高度变化 1,因此 bf 的变化量为 1,原有的 |bf| ≤ 1 最多被推到 2)。按照"新出现的节点位于失衡节点的哪一侧、以及位于该侧孩子的哪一侧",失衡形态分为四种。以失衡节点 z 及其更高的那一侧孩子为观察对象:

形态 特征 修复方式
LL z 左重,z.left 也左重或等高 对 z 右旋,一次
RR z 右重,z.right 也右重或等高 对 z 左旋,一次
LR z 左重,z.left 右重 先对 z.left 左旋(转为 LL),再对 z 右旋
RL z 右重,z.right 左重 先对 z.right 右旋(转为 RR),再对 z 左旋

LL 与 RR 称为单旋(一次旋转即可修复),LR 与 RL 称为双旋(两次旋转)。双旋可以理解为:先通过一次旋转把"内侧"的失衡转为"外侧"的失衡,再用一次旋转修复后者。

四种形态的完整图示如下。T1 至 T4 表示子树,它们在键序上满足 T1 < x < T2 < y < T3 < z < T4。

LL:对 z 右旋

        z                                 y
       / \                              /   \
      y   T4          ──右旋(z)──►     x     z
     / \                              / \   / \
    x   T3                           T1 T2 T3  T4
   / \
  T1  T2

RR:对 z 左旋

      z                                    y
     / \                                 /   \
    T1  y            ──左旋(z)──►       z     x
       / \                             / \   / \
      T2  x                           T1 T2 T3  T4
         / \
        T3  T4

LR:先对 y 左旋,再对 z 右旋

        z                    z                    x
       / \                  / \                 /   \
      y   T4   ──左旋(y)──►  x  T4  ──右旋(z)──► y     z
     / \                    / \                / \   / \
    T1  x                  y  T3              T1 T2 T3 T4
       / \                / \
      T2  T3             T1 T2

RL:先对 y 右旋,再对 z 左旋

      z                    z                      x
     / \                  / \                   /   \
    T1  y   ──右旋(y)──►  T1  x    ──左旋(z)──► z     y
       / \                  / \               / \   / \
      x  T4                T2  y             T1 T2 T3 T4
     / \                      / \
    T2  T3                   T3 T4

四种形态的中序序列都是 T1 x T2 y T3 z T4,逐字未变。这一点是旋转能够"修复形状而不破坏语义"的根本原因,也是调试时的第一道校验:任何旋转实现若改变了中序结果,方向一定写错了。

2.3 插入后的回溯调整

插入的流程分两步:向下定位到插入位置,向上回溯更新高度并检查失衡。

insert(key):
    node = 递归定位并插入新叶子(此时的树可能暂时违反不变量)
    回溯过程中,对路径上的每个节点:
        重新计算高度
        若 |bf| ≤ 1,继续向上
        若 |bf| = 2,按四种形态旋转,并停止继续向上

插入只需一次重构。 这一点常被表述为"插入最多一次旋转",更准确的表述是"插入最多一次重构"——LL 与 RR 是 1 次旋转,LR 与 RL 是 2 次旋转,但都属于同一次重构。理由是:插入使某侧子树高度增加 1,而修复用的旋转把该子树的高度恢复到插入之前的值。以 LL 为例:

插入前:z 高度 = 2(左右子树高度 1 与 1)          旋转前:z 高度 = 3(2 与 1)
旋转后:y 高度 = 2,与原 z 的高度一致

子树高度既已恢复,z 之上所有祖先的高度就不会因这次插入而变化,其平衡因子自然不会被破坏。因此第一次触发旋转的节点就是最高的一处失衡点,修复后回溯可以立即终止。

这一结论有前提:新节点沿路径下降时,路径上每个节点的高度都增加 1,但只有最低的那个"从平衡变为失衡"的节点需要旋转。路径下方若有节点失衡,修复它之后上方就不受影响。因此插入的调整是自底向上、命中即止的。

2.4 删除后的级联旋转

删除的调整方向与插入相反:删除可能引发沿路径向上传播的多次旋转。

原因是删除使某侧子树高度减少 1,修复用的旋转虽然恢复了该节点的平衡,但可能使子树的高度比删除前** умень了 1**,于是其父节点的平衡因子继续被推向失衡。

        g                            g
       / \                          / \
      z   T4      ──删除 T1 中的叶子──►  z   T4    ...  z 失衡并旋转
     / \                              / \
    y   T3                           y   T3
   / \
  T1  T2                          (T1 的高度减少 1)

旋转后的高度是否恢复,取决于旋转轴上那个孩子的平衡因子:

失衡节点 z 的 bf 较高侧孩子 y 的 bf 旋转后的子树高度 是否需要继续向上回溯
±2 ±1 比删除前减少 1 需要
±2 0 与删除前相同 不需要,可以停止

第二行的情形只可能在删除中出现,插入中不会发生:插入引起的失衡节点的较高侧孩子必定是 ±1(外侧或内侧),而删除可能使该孩子恰好变为等高。这一情形下的单旋仍然是单旋(不转为双旋),但旋转后子树高度不变,因此沿路径向上的失衡不再传播。

结论是:AVL 树删除的旋转次数上界为 O(log n),即每个祖先节点都可能需要一次重构。这是 AVL 树在写多场景下的主要弱点,也是红黑树把旋转次数压到常数次所要解决的问题。

2.5 旋转顺序不变的意义

把 2.2 节的结论提炼出来,可以得到旋转操作的三条性质,它们构成了所有平衡树实现与调试的基础:

  1. 中序序列不变。旋转不跨越任何键的相对次序,因此有序性自动保持,无需任何额外的比较或重排。
  2. 只改动常数个指针。一次旋转涉及 2 个节点的父子关系与 3 条子树指针,代价与树规模无关。
  3. 树高变化可预测。旋转后子树的高度要么不变,要么减少 1,因此是否继续向上修复可以精确判断(2.4 节的表格就是这一判断的量化)。

这三条性质使旋转成为"局部可逆的塑形操作":正确的旋转序列无论怎样组合,都不会破坏有序性;而错误的旋转(方向写反、指针漏改)会立即破坏有序性或高度字段的一致性,因此在调试中表现为两种可检测的症状(见第三章第 4 节与第 5 节)。

3. 红黑树

红黑树(Red-Black Tree)由 Guibas 与 Sedgewick 在 1978 年提出,用颜色而非高度来表达平衡约束。它的平衡条件不如 AVL 直观,但换来了两个结果:旋转次数为常数,以及可以用一个颜色位表达全部平衡状态。

3.1 五条性质及其含义

红黑树在二叉搜索树上附加五条性质:

  1. 每个节点是红色或黑色。颜色是节点的唯一附加信息,一个二进制位。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL,空指针所指向的哨兵)是黑色。(若实现中不设哨兵而直接用 null 表示空,则约定空指针视为黑。)
  4. 红色节点的两个子节点都是黑色,即不存在父红子红这样的连续红节点。
  5. 从任一节点出发到其所有叶子的路径上,黑节点数目相同,即同一节点的黑高唯一。

五条性质的作用可以逐条对应到结构上:

性质 直接作用
1 提供"颜色"这一附加状态,使平衡信息可以局部表达与局部修复
2 消除根处的边界情形,使修复过程不必为根单独判断
3 使黑高的计数有统一的终点,性质 5 才得以表述
4 限制红节点的密度,限制最长路径的长度
5 保证所有路径的"有效深度"一致,限制最短路径与最长路径的比值

性质 4 与性质 5 的组合是全部结论的来源。两者共同给出 1.2 节推导的最长路径不超过最短路径的两倍与树高上界 2 log₂(n + 1)。因此红黑树是一棵"高度近似平衡"的 BST:局部看,相邻两条路径的长度可以相差近一倍;全局看,树高仍是对数级。

需要强调的是,性质 4 与性质 5 都不是关于高度的直接约束,这是红黑树与 AVL 的根本差别。修复操作因此也不需要知道任何高度信息,只需要检查颜色,这就是旋转次数能够压到常数次的原因。

3.2 从 2-3-4 树理解红黑树

五条性质本身不直观,但如果不把它们当作"凭空规定的规则",而是当作一棵 2-3-4 树的二叉表示,全部规则都能得到解释。

2-3-4 树是 4 阶 B 树:每个节点容纳 1 至 3 个键,因而有 2、3 或 4 个孩子,所有叶子在同一层。它有两条性质:节点内键有序、所有叶子等深。2-3-4 树是天然平衡的(叶子等深),但一个节点要容纳多个键,用二叉节点无法直接表示。

红黑树的思路是:用"黑节点 + 其红孩子"来表示 2-3-4 树中的一个多键节点。红节点不构成独立的 2-3-4 节点,它与自己的黑父节点合起来代表同一个节点。

2-3-4 树的节点 红黑树的对应形状
2-节点(1 键 2 子) 一个黑节点,两个孩子均为黑
3-节点(2 键 3 子) 一个黑节点带一个红孩子(红孩子在左或在右)
4-节点(3 键 4 子) 一个黑节点带左右两个红孩子

按这一对应关系,五条性质都成为 2-3-4 树性质的翻译:

红黑树性质 2-3-4 树中的含义
4(无连续红节点) 一个 2-3-4 节点最多容纳 3 个键,即不存在"5-节点"
5(黑高相同) 所有叶子在同一层
3(叶子为黑) 叶子层是统一的终止层
2(根为黑) 根节点唯一,不需要与父节点合并

插入的调整也直接对应 2-3-4 树的操作。 2-3-4 树插入时会遇到节点已满(4-节点)的情形,处理方式是把这个 4-节点分裂,中间的键上移到父节点;若父节点也因此变满,分裂继续向上传播。红黑树的插入调整正是这一过程:

2-3-4 树中的动作 红黑树中的动作 红黑树中的情形
插入后节点未满 新节点染红,父为黑,无冲突 无需调整
4-节点分裂,中间键上移 父与叔由红变黑,祖父由黑变红 情形 1(变色)
分裂导致父节点内键序需要重排 对父与祖父旋转 情形 2 与情形 3(旋转)
分裂继续向上传播 把祖父作为新的当前节点继续判断 情形 1 的循环

删除同样对应。 2-3-4 树删除一个键后若节点键数不足(只有 1 个键却还要被删除,节点会变成空),需要向兄弟节点"借"一个键(对应红黑树的旋转与变色),或与兄弟合并(对应红黑树的变色上移)。这一组操作比插入复杂,是红黑树删除实现困难的根源。

这一等价关系带来两个实用推论:

  1. 可以把红黑树的调整逻辑理解为"在 2-3-4 树上做局部修正",从而减少对五条性质的逐条背诵。凡是"需要分裂"或"需要借键"的时刻,红黑树中必然出现一次变色或旋转。
  2. 不同的等价方式导出不同的红黑树变体。上表描述的是经典 2-3-4 表示(Java 的 TreeMap、C++ 的 std::map 采用这一体系);若改用 2-3 树表示(节点只容纳 1 至 2 个键),得到的是左倾红黑树(LLRB)——要求红孩子只能是左孩子,插入与删除的代码分支更少,但每棵红黑树对应的结构不再唯一。两种变体的性质与复杂度上界相同,差别在实现分支数。

3.3 插入的三种情形

插入分两步:按 BST 方式插入新节点并染红,然后自底向上修复。

新节点染红的理由与 2-3-4 树的等价关系一致:新插入的键先假设属于某个已有的 2-3-4 节点(即与某个黑节点合并),因此不引入新的黑节点层,性质 5 自动保持。若父节点为黑,插入直接完成;若父节点为红,则违反性质 4,需要修复。

设当前节点为 z,父节点为 p,祖父为 g,叔节点(p 的兄弟)为 u。由于 p 为红,g 必为黑(性质 4),因此 u 的颜色是唯一需要判读的外部信息。三种情形如下(下图以 p 是 g 的左孩子为例,p 是右孩子时左右对称)。

情形 1:叔节点 u 为红

        g(黑)                        g(红)
       /    \                      /      \
     p(红)  u(红)   ──变色──►    p(黑)    u(黑)
     /                            /
   z(红)                        z(红)

把 g 当作新的当前节点,继续向上判断

处理方式是变色:p 与 u 转黑,g 转红。这一操作对应 2-3-4 树中 4-节点的分裂——中间键上移,两侧的键各自成为独立的 2-节点。变色后 g 变红,若 g 的父节点也是红,冲突上移一层,因此需要把 g 作为新的当前节点继续检查。变色过程可能一直传播到根,此时把根染黑即可(性质 2)。

情形 1 只变色、不旋转,但可能重复 O(log n) 次。

情形 2:叔节点 u 为黑,z 是 p 的内侧孩子

      g(黑)                     g(黑)
     /    \                    /    \
   p(红)  u(黑)  ──左旋(p)──► z(红)  u(黑)      z 成为外侧孩子
   / \                        / \
  T1  z(红)                 p(红) T3
     / \                    / \
    T2  T3                 T1  T2

随后按情形 3 处理

处理方式是对 p 旋转一次(z 是 p 的右孩子则左旋),把内侧失衡转为外侧失衡,然后转入情形 3。这一旋转不改变颜色,只是重排形状。

情形 3:叔节点 u 为黑,z 是 p 的外侧孩子

      g(黑)                       p(黑)
     /    \                      /      \
   p(红)  u(黑)  ──右旋(g)──►  z(红)    g(红)
   / \                          / \      / \
  z(红) T3                     T1 T2    T3  u(黑)
  / \
 T1  T2

同时:p 染黑、g 染红,旋转后 p 成为子树根

处理方式是 p 染黑、g 染红,然后对 g 旋转。旋转与变色完成后,子树的根变为黑,其两个孩子均为黑,性质 4 与性质 5 都得到恢复,修复结束,不需要继续向上。

三种情形的代价对比:

情形 是否旋转 是否继续向上 对应 2-3-4 树的动作
1(叔红) 否 是,把 g 作为新当前节点 4-节点分裂,中间键上移
2(内侧) 是,1 次 否,转入情形 3 节点内键序重排
3(外侧) 是,1 次 否,修复结束 分裂完成

因此插入的旋转次数不超过 2 次(情形 2 一次加情形 3 一次),而变色次数可能为 O(log n)。这与 AVL 插入的"一次重构、高度恢复即止"在效果上接近,区别在于红黑树用变色代替了 AVL 的高度更新,且不需要读取任何高度信息。

3.4 删除的困难与调整思路

删除是红黑树实现中最容易出错的部分,困难来自两处。

困难一:被删位置可能有两个孩子。 被删除的节点若有左右两个孩子,直接摘除会留下两个待接的子树。标准做法是用中序后继(右子树的最左节点)替换被删位置的内容,然后转为删除那个后继节点。后继节点至多有一个孩子(它没有左孩子),因此问题被归约为"删除至多有一个孩子的节点":

删除 z:
    若 z 有两个孩子:
        取后继 s(z 右子树的最左节点)
        把 s 的键与值复制到 z 的位置
        转为删除 s(此时的 s 至多有一个右孩子)
    摘除至多一个孩子的节点:用其唯一的孩子(或哨兵)顶替它的位置

内容替换而非节点替换,是实现上的常见做法,代价是键值被搬移一次。节点替换(改父指针、改孩子指针)的写法在带迭代器或外部引用的情况下更安全。

困难二:被删节点的颜色决定是否需要修复。 若被删节点是红色,摘除它不改变任何路径上的黑节点数目,性质 5 保持,直接结束。若被删节点是黑色,则经过它的所有路径都少了一个黑节点,性质 5 被破坏,需要修复。

修复的对象是顶替上来的那个节点(记作 x)。它现在"缺"一个黑节点,这一状态称为双黑(double black)。修复的目标是把多出来的这个黑色沿着树传递出去,直到传递到根(此时把根染黑即可)或传递到一个红节点(此时把它染黑即可)。

设 x 的兄弟为 s(同侧的孩子),修复分为四种情形(以 x 是左孩子为例):

情形 条件 处理 是否结束
1 兄弟 s 为红 s 染黑,父染红,对父左旋;重取新的 s 转为情形 2、3 或 4
2 s 为黑,s 的两个孩子都为黑 s 染红,把 x 上移到父节点,继续判断 可能沿路径向上传播
3 s 为黑,s 的远侄(s.right)为黑、近侄(s.left)为红 近侄染黑,s 染红,对 s 右旋;重取新的 s 转为情形 4
4 s 为黑,s 的远侄为红 s 取父的颜色,父染黑,远侄染黑,对父左旋 结束

四种情形的形状与插入的三种情形高度相似(同样是"红叔 / 侄全黑 / 内侧 / 外侧"的分类),区别在于插入只在一处结束,而删除的情形 2 会继续向上传播。

删除的旋转次数不超过 3 次(情形 1、情形 3、情形 4 各至多一次),变色次数可能为 O(log n)。于是两种树在旋转次数上的对比是:

操作 AVL 树 红黑树
插入 至多 1 次重构(含双旋至多 2 次单旋) 至多 2 次旋转
删除 至多 O(log n) 次重构 至多 3 次旋转
其他调整 沿路径更新高度,O(log n) 次 沿路径变色,O(log n) 次

插入上两者接近,删除上红黑树明显占优。这是红黑树被标准库广泛采用的核心原因。

工程实现的细节(哨兵节点、父指针维护、TreeMap 的 fixAfterDeletion 分支组织)见第三章第 2 节;TreeMap 的五条性质表述与复杂度表见 Java 集合框架实现原理 第 5.1 节。

3.5 树高上界的工程含义

把 3.1 节的推导落成可以使用的数值:

n log₂(n+1) AVL 上界(1.44 log₂n) 红黑树上界(2 log₂n) 两者比较次数之差
10³ 10 14 20 最多 6 次比较
10⁶ 20 28 40 最多 12 次比较
10⁹ 30 43 60 最多 17 次比较

两点工程含义:

  1. 绝对差值是"最坏情况下的比较次数差",不是平均差。红黑树的平均路径长度明显短于上界(随机键的平均深度约为 2 log₂n 量级中的较低值),实测差距通常小于上表的差值。这与复杂度分析中"上界不等于实际值"的一般情形一致(见 复杂度与算法分析 第 2.3 节)。
  2. 即使按最坏情况计,差值也是常数级别。两类树的树高都是 O(log n),上界之比是常数 1.39。因此选型不能只看树高,还要看更新时的调整量、实现复杂度与并发需求。

4. 对比与选择

4.1 逐项对比

维度 AVL 树 红黑树
平衡约束 每个节点左右子树高度差不超过 1 五条颜色性质,间接约束
树高上界 约 1.44 log₂n 约 2 log₂n
查找代价 更优(树高更小) 略劣(树高更大)
插入旋转次数 至多 1 次重构(LR 与 RL 含 2 次单旋) 至多 2 次旋转
删除旋转次数 至多 O(log n) 次重构 至多 3 次旋转
插入后的调整传播 一次重构后高度恢复,即止 情形 1 的变色可能传播到根
删除后的调整传播 旋转可能级联,每个祖先都可能需要 情形 2 的变色可能传播到根
每个节点的额外信息 高度字段(或 2 位平衡因子) 1 位颜色
实现复杂度 插入简单、删除中等 插入中等、删除复杂
结构是否唯一 是(给定键集合,平衡后的形状由插入顺序与旋转策略确定,但约束唯一) 否(同一键集合可有多种合法着色)
典型落点 内存中的查找密集结构、需要严格高度上界的场景 标准库的有序映射(TreeMap、std::map)、需要频繁更新的索引

4.2 取舍的依据

读多写少选 AVL。 AVL 的树高上界比红黑树低约 30%,查找路径更短;插入的调整量(一次重构)与红黑树接近。若负载以查找为主、更新占比很低,AVL 的树高优势可以直接转化为吞吐优势。

写多读少或读写混合选红黑树。 决定性差异在删除:AVL 的删除可能沿路径级联旋转,最坏 O(log n) 次,每次旋转都要改写指针并更新高度字段;红黑树的删除旋转次数上界为 3 次,且旋转只改写指针与颜色位。在更新占比高的负载中,前者的常数开销会被放大。

需要确定性上界的场景需要分别评估。 两种树的树高都有确定上界,因此单次操作的最坏延迟可以推导,这一点优于跳表。但"最坏延迟"要按各自的旋转次数上界计算,AVL 删除的 O(log n) 次旋转在硬实时场景中需要单独评估。

实现复杂度在两者之间的差距不对称。 AVL 的插入实现可以做得很短(四种形态的旋转、命中即止的回溯);红黑树的删除实现是公认的难点(双黑修复的四种情形、情形的转换与终止条件)。若团队需要自行维护一份平衡树实现,AVL 的插入部分更易写对,而红黑树的删除部分更容易在边界上出错。

但两者在量级上相同。 树高都是 O(log n),四类操作都是 O(log n)。差别落在常数因子、树高系数与旋转次数上,属于必须实测才能给出结论的情形,不能仅凭上界的比值外推(见第三章第 3 节与 复杂度与算法分析 第 2.7 节)。

4.3 选择时的判据

需求 建议
只读或极少量写入的有序映射 AVL 树
读写混合、更新占比超过约 10% 的有序映射 红黑树
删除操作占比较高 红黑树
需要最严格的树高上界 AVL 树
需要复用语言提供的实现 红黑树(标准库的有序映射基本都是红黑树或其他近似平衡结构)
需要并发有序访问 跳表(红黑树的无锁实现困难,见 Java 并发编程)
需要按排名访问或区间聚合 两种树都需要额外维护子树信息,可自行实现或在跳表与专门结构中选择
数据静态、构造后不改动 有序数组加二分,空间更紧凑、缓存更友好

5. 其他平衡结构概览

AVL 与红黑树之外,还有若干以不同方式实现"高度受控"的结构。它们与两种经典树的差别,恰好能说明平衡约束的不同设计空间。

5.1 Treap:用随机优先级替代平衡条件

Treap 是"树堆"(Tree + Heap):每个节点同时持有一个键与一个随机优先级,键满足 BST 序,优先级满足堆序(通常小根堆)。由于优先级是插入时随机生成的、与键无关,给定的键集合与优先级集合所决定的 Treap 形状唯一,且这个形状与"按随机顺序插入同一批键所得到的 BST 形状"分布相同。

由此得到两条结论:

  1. 期望树高为 O(log n),与随机插入顺序的 BST 期望树高一致;无需维护任何平衡因子或颜色。
  2. 不存在能构造出退化输入的键序列,因为形状由随机优先级决定,与键的取值和插入顺序无关。这一点与跳表相同(见 跳表 第 1.3 节与第 2.2.4 节)。

修复手段是把优先级违反堆序的节点通过旋转上移,直到满足堆序:

def insert(self, node, key):
    if node is None:
        return Node(key)                       # 新节点的优先级在构造时随机生成
    if key < node.key:
        node.left = self.insert(node.left, key)
        if node.left.prio < node.prio:         # 左孩子优先级更高,需要上移
            node = self.rotate_right(node)
    else:
        node.right = self.insert(node.right, key)
        if node.right.prio < node.prio:
            node = self.rotate_left(node)
    return node

Treap 没有删除时的级联问题:删除通过"把节点旋转到叶子再摘除"或"合并两棵子树"完成,旋转次数期望为 O(log n)。它的另一个优势是支持**分裂(split)与合并(merge)**两个 O(log n) 的操作,因而适合实现可持久化结构、按区间切分的容器。

代价是:结论是期望而非最坏,随机源必须独立于键(与跳表同样的注意事项)。

5.2 替罪羊树:不立即旋转,事后重建

替罪羊树(Scapegoat Tree)放弃"每次更新都维持精确平衡",改为设定一个容忍参数 α(通常取 0.7 至 0.75),要求每个节点的子树规模与孩子子树规模满足

size(node.left) ≤ α · size(node)  且  size(node.right) ≤ α · size(node)

插入时不做任何旋转,直接按 BST 插入并把路径上的规模计数加一。若某个祖先违反上述约束,就把这个祖先为根的整棵子树重建为完全平衡的形态——这个被选中的祖先就是"替罪羊"。

  • 优点:插入的常规路径没有任何旋转,只需逐层加计数;删除可以用标记延后处理;实现比红黑树直观得多。
  • 代价:重建子树的代价为 O(k)(k 为该子树规模),但触发频率随 α 的取值受控,摊还代价为 O(log n)。单次插入的最坏代价因此不是 O(log n),而是与子树规模同阶。
  • 适用:对摊还代价可接受、对实现简单性要求高、且插入与删除频率相近的场景。

替罪羊树与 AVL 的差别是"精确平衡 + 少量旋转"与"容许偏差 + 偶尔重建"的差别,与跳表用概率替代比例的思路属于同一类取舍——把持续性约束换成偶发性的修正。

5.3 Splay 树:把访问过的节点旋转到根

Splay 树(伸展树)不维护任何显式平衡信息,唯一的操作是伸展(splay):每次访问一个节点后,通过一系列旋转把它移动到根,同时把访问路径上的结构重新组织。

  • 摊还代价为 O(log n)(每次操作的摊还分析为 O(log n),单次操作最坏为 O(n))。
  • 利用访问局部性:最近访问过的节点靠近根,重复访问的代价极低。适合有倾斜访问分布的场景(热点数据)。
  • 不需要额外字段,每个节点只有键、值与左右指针,内存开销最小。
  • 两个已知缺点:单次操作无最坏保证;写操作(即使只读也必须旋转)会改变结构,因此不适合读并发场景。

Splay 树的摊还分析是复杂度分析中势能法的经典用例,其证明口径与"均摊不等于每次都快"的区分见 复杂度与算法分析 第 2.3 节与第 3.2 节。

5.4 跳表:概率平衡

跳表用随机层数替代旋转与着色,在期望意义上取得与平衡树相同的对数级代价,最坏情况为 O(n)。它与本节其他结构的核心差别在于平衡机制的位置:平衡树把平衡信息存放在节点的字段里(高度、颜色、规模),跳表把平衡信息存放在节点的"高度分布"里,由随机数决定。

维度 AVL / 红黑树 Treap 替罪羊树 Splay 树 跳表
平衡手段 高度差 / 颜色约束 随机优先级 规模约束 + 事后重建 访问即伸展 随机层数
最坏代价 O(log n) O(n)(期望 O(log n)) 摊还 O(log n) O(n)(摊还 O(log n)) O(n)(期望 O(log n))
查找时是否改结构 否 否 否 是 否
每个节点额外信息 高度字段 / 1 位颜色 1 个优先级 1 个规模计数 无 层数数组
按排名访问 需额外维护子树规模 需额外维护规模 天然有规模计数 需额外维护 span 字段直接支持
并发友好性 差(旋转影响范围大) 差 差 差 好(局部指针 CAS)

跳表的完整原理、随机层数的分布分析、与平衡树在实现成本与并发上的逐项对比见 跳表 第 2.6 节与第 3.6 节。

5.5 多叉平衡树在存储系统中的位置

上述结构全部是二叉的,节点在堆上离散分配。当数据量大到无法全部驻留内存,或者主要代价来自磁盘与闪存的块访问次数时,二叉结构不再适用:树高随行数增长(千万行对应 20 余层),每一层都意味着一次随机 IO,累计的 IO 次数无法接受。

多叉平衡树(B 树、B+ 树)的做法是让一个节点占用一个页(常见 4 KB 至 16 KB),页内可以容纳几十至上千个键,扇出因此很大。以扇出 500 计算:3 层可索引约 1.25 亿行,4 层可索引约 625 亿行。树高被压在 3 至 4 层,一次查找只需 3 至 4 次页访问。

维度 二叉平衡树 B+ 树
节点规模 1 个键,2 个孩子 一页,几十至上千个键
树高(10⁸ 键) 约 28 至 40 层 3 至 4 层
单次查找的介质访问 约 28 至 40 次指针跳转(内存中) 3 至 4 次页读取(磁盘上)
页内查找 不适用 页内二分或顺序查找,通常只占一次块访问
顺序扫描 中序遍历,指针跳转频繁 叶节点用双向链表串联,顺序 IO
更新时的传播 旋转(本地) 页分裂与页合并(可向上传播)

多叉平衡树与二叉平衡树的关系,可以概括为"把树高换成扇出":扇出增大使树高下降,代价是节点内部的组织成本与分裂合并的维护成本。这也是磁盘索引默认使用 B+ 树而非红黑树的原因,相关工作原理与索引结构对照见 MySQL 索引与执行计划;B 树与 B+ 树的定义、节点组织、分裂与合并以及树高估算见 B 树与 B+ 树。

在内存中,二叉平衡树与多叉结构的选择则相反:节点大小超过一个缓存行时,页内查找的额外成本超过了树高降低带来的收益,因此内存中的有序结构仍以二叉平衡树、跳表与有序数组为主。

5.6 结构谱系

把本节的结构按"平衡信息的来源"排列,可以得到一条清晰的谱系:

确定性约束 + 精确平衡     AVL 树(高度差 ≤ 1)
确定性约束 + 近似平衡     红黑树(颜色性质)、多叉平衡树(页内扇出)
松弛约束 + 事后修正       替罪羊树(规模约束 + 重建)、Splay 树(访问后伸展)
概率约束                  跳表(随机层数)、Treap(随机优先级)

越靠上,最坏保证越强,更新时的调整逻辑越复杂;越靠下,实现越简单、并发越友好,但保证从"最坏"弱化为"期望"或"摊还"。选型的实质是决定需要哪一种保证:需要可推导的最坏延迟就取上两行;可以接受期望或摊还结论、更看重实现与并发,则取下两行。

6. 与工程实现的关系

6.1 标准库中的有序映射

绝大多数业务代码接触平衡树的方式,是使用语言标准库提供的有序映射与有序集合。这些实现的底层基本都是红黑树或其变体:

语言与实现 底层结构 说明
Java TreeMap / TreeSet 红黑树(2-3-4 表示) TreeSet 是 TreeMap 的薄封装,元素作键,值填充哨兵对象
C++ std::map / std::set 红黑树 标准未强制规定,主流实现(libstdc++、libc++、MSVC STL)均为红黑树
C++ std::multimap 红黑树 允许重复键
Linux 内核 rbtree 红黑树 进程调度、虚拟内存区域管理、定时器
Java HashMap 的树化桶 红黑树 桶内链表过长时的兜底结构
.NET SortedDictionary 红黑树 .NET 另有基于 B+ 树的 ImmutableSortedDictionary

标准库选择红黑树而非 AVL,理由与 4.2 节的结论一致:通用容器无法预知使用者的读写比例,而红黑树在最坏情况下的更新代价明显更好(删除旋转次数为常数),且额外空间只需一个颜色位。查找路径略长带来的损失,在整个容器 API 的使用分布中不占主导。

TreeMap 的完整实现要点(红黑树五条性质、树高 O(log n) 的复杂度表、headMap 与 ceilingKey 等导航方法、比较器语义)见 Java 集合框架实现原理 第 5.1 节与第 5.2 节。

6.2 哈希冲突时的树化

散列表在冲突严重时会用红黑树兜底,这是平衡树在标准库中的第二处落点。HashMap 的桶内结构转换条件是:

常量 值 作用
TREEIFY_THRESHOLD 8 桶内链表节点数达到该值时尝试树化
UNTREEIFY_THRESHOLD 6 桶内树节点数降到该值时退化回链表
MIN_TREEIFY_CAPACITY 64 允许树化的最小表容量

即"桶内节点数达到 8 且 表容量不小于 64"才真正树化;容量不足时改为扩容。完整的阈值推导(负载因子 0.75 下桶内 8 个节点的概率约为 6×10⁻⁸,树化只是防御性兜底)见 Java 集合框架实现原理 第 3.3 节与第 3.4 节,桶内结构的对照见 散列表 的哈希攻击与防护一节。

这里有三点与本文直接相关:

  1. 为什么选红黑树而不是 AVL。桶内结构的访问模式以"插入与删除交替"为主(哈希表的增删频繁),AVL 删除的级联旋转在这个场景下代价偏高;红黑树的删除旋转次数为常数,更适合。同时红黑树只需一个颜色位,而 HashMap 的桶节点还需要承载链表顺序与扩容拆分的额外指针,内存本就紧张。
  2. 为什么桶内结构的树化在容量不足时被推迟。容量小于 64 时冲突的根因是表太短,扩容摊开元素比在短表上维持红黑树更划算。这与 4.1 节的结论一致:平衡树解决的是"在同一批元素上维持对数级深度",而扩容解决的是"元素是否放错了位置"。
  3. 树化节点比链表节点大得多。HashMap.Node 约 32 字节,树化后的 TreeNode 约 48 字节(多出左右子指针、父指针与颜色位)。因此树化是兜底而非默认:正常散列分布下绝大多数桶只有 0 至 2 个节点,不会进入树化分支。

6.3 为什么多数业务代码无需手写

综合以上,自行实现平衡树的必要性很低,理由是:

  1. 标准库的接口已经覆盖常见需求。有序遍历、范围查询(headMap、tailMap、subMap)、邻近查询(ceilingKey、floorKey、higherKey、lowerKey)、最值查询(firstKey、lastKey)在 TreeMap 上都是 O(log n)。这些覆盖了有序映射的绝大多数用法。
  2. 手写实现的正确性成本极高。红黑树的删除涉及双黑修复的四种情形及其转换,任一边界写错都会在特定操作序列下破坏不变量,而这类错误往往不在常规用例中暴露(见第三章第 5 节)。
  3. 性能收益通常不存在。标准库实现经过长期优化,泛型与内联保证了比较与指针操作的常数开销接近手工实现;自行实现的常见后果是把 O(log n) 写成 O(n) 或引入难以复现的缺陷,而不是获得性能提升。

需要自行实现的场景是标准库不提供的操作,见第三章第 4 节。


三、实现

1. AVL 实现要点

1.1 节点结构与辅助函数

采用"保存高度"的做法。空节点高度为 0,单节点高度为 1,三个辅助函数把高度与平衡因子的读取集中在一处,使后续的旋转与回溯代码只依赖这三个函数:

final class AvlNode<K, V> {
    K key;
    V value;
    AvlNode<K, V> left, right;
    int height;                    // 空节点为 0,单节点为 1

    AvlNode(K key, V value) {
        this.key = key;
        this.value = value;
        this.height = 1;
    }
}

private static int height(AvlNode<?, ?> n) {
    return n == null ? 0 : n.height;
}

// 在子树结构改变后重算高度,必须先于上层节点调用
private static void updateHeight(AvlNode<?, ?> n) {
    n.height = 1 + Math.max(height(n.left), height(n.right));
}

// 平衡因子:正为左重,负为右重,合法取值为 -1、0、1
private static int balanceFactor(AvlNode<?, ?> n) {
    return height(n.left) - height(n.right);
}

三个约定的作用需要明确:

  • 空节点高度取 0 而不是 −1。这样"单节点高度为 1"与"平衡因子 = 高度差"两个公式都不需要为空树开特例。若取 −1,则单节点高度为 0,输出与比较时容易与"空树"混淆。
  • 高度由子节点推出,不累加不缓存。任何改变子树的指针改写之后必须调用 updateHeight,这是实现中最容易遗漏的一步(见第 5 节)。
  • 平衡因子不单独存储。每次现算,代价是两次字段读取与一次减法;换来的是"高度字段若不同步,平衡因子必然同时出错"——两类错误合并为一类,便于校验。

1.2 两种旋转的代码结构

四种形态的旋转由两个基本旋转组合而成。先给出单旋:

// 右旋:把 y 的左孩子 x 提升为子树根;返回新的子树根,由调用者接回原位置
private AvlNode<K, V> rotateRight(AvlNode<K, V> y) {
    AvlNode<K, V> x = y.left;
    AvlNode<K, V> t2 = x.right;
    x.right = y;              // y 降为 x 的右孩子
    y.left = t2;              // x 原有的右子树挂到 y 的左侧(保持键序)
    updateHeight(y);          // 先更新降下去的那个
    updateHeight(x);          // 再更新升上来的那个
    return x;
}

// 左旋:把 y 的右孩子 x 提升为子树根
private AvlNode<K, V> rotateLeft(AvlNode<K, V> y) {
    AvlNode<K, V> x = y.right;
    AvlNode<K, V> t2 = x.left;
    x.left = y;
    y.right = t2;
    updateHeight(y);
    updateHeight(x);
    return x;
}

代码结构上有四处固定要求:

  1. 指针改写顺序固定为"先接管子树,再改写父子"。以上例为例,t2 必须在 x.right = y 之前或之后取到,且必须在 y.left = t2 之前取出。若先执行 x.right = y 再取 x.right,取到的是 y 而非原来的 t2,结构即刻被破坏。
  2. 高度更新顺序固定为"先下层后上层"。y 旋转后成为 x 的孩子,其高度必须先用新的子树重算,x 的高度才能基于正确的 y.height 计算。顺序反了会得到偏大或偏小的高度,进而使平衡因子判读失准。
  3. 旋转函数返回新的子树根。这是递归实现能够把子树接回父节点的前提,也是避免维护父指针的关键约定。
  4. 单旋不判断失衡类型。rotateRight 只负责"提升左孩子",至于调用它是因为 LL 还是 LR 的第二步,由调用方决定。

四种形态由这两个基本旋转组合,无需为每种形态单独编写旋转:

LL:rotateRight(z)
RR:rotateLeft(z)
LR:z.left = rotateLeft(z.left);  rotateRight(z)
RL:z.right = rotateRight(z.right); rotateLeft(z)

注意 LR 的第一步是把 rotateLeft 的返回值接回 z.left,而不是直接对 z 操作。漏掉这一步的赋值是最常见的实现错误之一(见第 5 节)。

1.3 插入的递归实现与回溯

递归实现让"回溯"天然发生:每层调用在返回前更新自己的高度并检查失衡,等价于自底向上遍历路径。

private AvlNode<K, V> insert(AvlNode<K, V> node, K key, V value) {
    if (node == null) {
        return new AvlNode<>(key, value);      // 定位到空位,挂上新叶子
    }
    int cmp = compare(key, node.key);
    if (cmp < 0) {
        node.left = insert(node.left, key, value);
    } else if (cmp > 0) {
        node.right = insert(node.right, key, value);
    } else {
        node.value = value;                     // 键已存在:只更新载荷,结构不变
        return node;
    }
    updateHeight(node);
    return rebalance(node);                     // 回溯时更新高度并修复失衡
}

// 按平衡因子与较高侧孩子的平衡因子判断形态并旋转
private AvlNode<K, V> rebalance(AvlNode<K, V> node) {
    int bf = balanceFactor(node);
    if (bf > 1) {                                        // 左重
        if (balanceFactor(node.left) < 0) {              // 内侧:LR
            node.left = rotateLeft(node.left);
        }
        return rotateRight(node);                        // LL 或 LR 的第二步
    }
    if (bf < -1) {                                       // 右重
        if (balanceFactor(node.right) > 0) {             // 内侧:RL
            node.right = rotateRight(node.right);
        }
        return rotateLeft(node);                         // RR 或 RL 的第二步
    }
    return node;                                         // 未失衡,原样返回
}

为什么这段代码在插入时只会旋转一次。 结构上没有提前 return,但旋转一旦发生,rebalance 返回的子树高度与插入前相同(见第二章 2.3 节的图示)。该子树的高度未变,其父节点的高度与平衡因子就不会被这次插入改变,因此上层的 rebalance 会全部落在 |bf| ≤ 1 的分支上,不会再次旋转。"命中即止"是高度恢复的推论,不需要额外的标志位或提前返回。

这一性质也带来一个实用的调试手段:在这段代码中加计数器,统计一次 insert 调用内发生旋转的次数。若某次插入的旋转次数大于 1,说明高度字段或平衡因子的判读出错。

1.4 删除的递归实现与级联

删除与插入共用同一套回溯框架,唯一的差别是不能提前终止:删除可能引发沿路径向上的多次旋转。

private AvlNode<K, V> delete(AvlNode<K, V> node, K key) {
    if (node == null) {
        return null;                            // 键不存在
    }
    int cmp = compare(key, node.key);
    if (cmp < 0) {
        node.left = delete(node.left, key);
    } else if (cmp > 0) {
        node.right = delete(node.right, key);
    } else {
        if (node.left == null) {                // 至多一个孩子
            return node.right;
        }
        if (node.right == null) {
            return node.left;
        }
        AvlNode<K, V> successor = min(node.right);   // 两个孩子:用中序后继替换内容
        node.key = successor.key;
        node.value = successor.value;
        node.right = delete(node.right, successor.key);
    }
    updateHeight(node);
    return rebalance(node);                     // 可能每个祖先都需要重构
}

三处与插入不同的地方:

  1. 删除的终止条件不能提前返回。rebalance 返回后必须继续把新的子树根接回上层并让上层继续检查。上述递归写法自然满足这一点——每层调用都在返回前执行 updateHeight 与 rebalance。
  2. 两个孩子的情形用后继替换内容。这样做避免了父指针的维护,代价是键值被复制一次。若结构上要求节点身份不变(外部持有节点引用),应改为节点替换的写法。
  3. 删除引发的旋转可能改变子树高度,因此不能像插入那样依赖"高度恢复"来跳过上层。第二章 2.4 节的表格给出了唯一的例外:当失衡节点的较高侧孩子平衡因子为 0 时,旋转后高度不变,此时可以提前终止;判断方法是在 rebalance 中比较旋转前后的 height,若相等则说明高度未变,可以向上返回一个标志以跳过后续的旋转。这一优化能减少删除路径上的旋转次数,但不是必经的优化。

1.5 边界处理

边界情形 处理要点
空树插入 直接返回新节点,不进入 rebalance
删除唯一节点 delete 返回 null,根指针需允许被置空
删除根节点且有两个孩子 后继替换内容后,转为删除后继(其后继无左孩子)
键重复 用计数(count)或允许重复值存在右子树;两种语义在删除时都需相应处理
键的比较结果为 0 但对象不相等 按"同一键"处理,与 TreeMap 的语义一致(见第 4 节)
键为 null 在 compare 中显式处理或直接拒绝,不能依赖自然比较
只有一个节点的子树失衡 不构成失衡(|bf| ≤ 1),rebalance 是恒等操作

2. 红黑树实现要点

2.1 哨兵节点的作用

红黑树的性质 3 要求"叶子(NIL)为黑"。实现上可以用 null 表示空,也可以用一个全局共享的哨兵节点表示所有空位:

private static final boolean RED = true;
private static final boolean BLACK = false;

final class RbNode<K, V> {
    K key;
    V value;
    RbNode<K, V> left, right, parent;
    boolean color;
}

// 哨兵:全局共享一个实例,颜色恒为黑,键值为空
private final RbNode<K, V> nil = new RbNode<>(null, null, BLACK);

哨兵的作用有四项:

  1. 消除空指针判断。判读"叔叔为黑"时,叔叔可能是空位,用哨兵则统一为读取 color 字段,不需要 uncle == null || uncle.color == BLACK 这样的复合条件。
  2. 使删除修复的边界统一。双黑修复需要判读"兄弟的两个孩子是否为黑",兄弟的孩子常为空位;若用 null,每一处判断都要加空值分支。
  3. 为黑高提供统一的终点。性质 5 的校验需要一个"黑节点"作为计数终点,哨兵恰好充当这一角色(见 2.4 节)。
  4. 根节点的父指针有落点。哨兵作为根的父节点,使 x.parent.parent 之类的连读在根附近仍然合法。

哨兵的代价是两处必须谨慎:

  • 哨兵是共享的,不能写入除颜色外的字段。删除修复中若需要把哨兵的父亲设为某个节点(部分教科书实现需要),这个写入会污染全局状态。稳妥的做法是让哨兵的 parent 保持固定值,并且在所有可能读到它的判断前先排除"当前节点是根"的情形。
  • 哨兵的左右指针应指向自身(或保持为空但永不访问),使"哨兵的左右孩子"这一读取不会崩溃。

java.util.TreeMap 采用的是不使用哨兵的写法,直接用 null 表示空位,并借助 parent 指针与额外的空值判断来处理边界。两种写法等价,区别是实现风格:哨兵减少分支但引入了共享可变状态的风险,null 写法分支多但每处状态都局部。

2.2 插入调整的代码框架

插入的调整框架完全由"父与叔的颜色判定"驱动。下例以 CLRS 的经典写法为骨架(z 为当前节点):

private void insertFixup(RbNode<K, V> z) {
    while (z.parent.color == RED) {              // 违反性质 4 才进入循环
        RbNode<K, V> p = z.parent;
        RbNode<K, V> g = p.parent;
        if (p == g.left) {
            RbNode<K, V> uncle = g.right;
            if (uncle.color == RED) {            // 情形 1:叔为红 → 变色并上移
                p.color = BLACK;
                uncle.color = BLACK;
                g.color = RED;
                z = g;                           // 冲突上移一层,继续判断
            } else {
                if (z == p.right) {              // 情形 2:内侧 → 先旋转转为情形 3
                    z = p;
                    rotateLeft(z);
                    p = z.parent;                // 旋转后父节点已改变
                }
                p.color = BLACK;                 // 情形 3:外侧 → 染色后对祖父旋转
                g.color = RED;
                rotateRight(g);
                // 旋转完成,子树根为黑、两子为黑,修复结束,循环条件不成立
            }
        } else {
            // p 是 g 的右孩子:与上文左右对称,rotateLeft 与 rotateRight 互换
        }
    }
    root.color = BLACK;                          // 性质 2:循环结束后确保根为黑
}

代码框架中的固定要点:

  1. 循环条件直接表达"违反性质 4"。不需要额外的标志位:只要父节点为红,性质 4 就被破坏,需要修复。
  2. 情形 2 之后必须重取父节点。rotateLeft(z) 改变了 z 与 p 的关系,此后 p 变量已经过期。这是该实现中最容易出错的细节。
  3. 情形 3 的染色对象是旋转前的 p 与 g。染色必须发生在旋转之前(或使用旋转前保存的引用),因为旋转会改变 g.parent。
  4. 循环结束后无条件把根染黑。情形 1 的传播可能一直到根,此时 z 为根且为红(由 g 上移而来),染黑即满足性质 2,且这一步使根的黑高增加 1,性质 5 仍然保持。
  5. 左右两份代码必须完全对称。建议把"哪一侧"抽成一个布尔量,用统一的旋转函数与镜像判断实现,减少写出不对称分支的机会(但要注意可读性,多数实现选择保留两份镜像代码)。

TreeMap 的对应实现是 fixAfterInsertion,其分支组织与上述框架一致,差别在于使用 null 表示空位并把左右情形写在同一段循环中(见 Java 集合框架实现原理 第 5.1 节)。

2.3 删除的替代节点与调整

删除分两段:先归约为"删除至多有一个孩子的节点",再按颜色决定是否修复。

private void deleteNode(RbNode<K, V> z) {
    if (z.left != nil && z.right != nil) {           // 两个孩子:用中序后继替换内容
        RbNode<K, V> s = successor(z);               // 右子树的最左节点
        z.key = s.key;
        z.value = s.value;
        z = s;                                       // 转为删除 s,它至多有一个右孩子
    }
    RbNode<K, V> child = (z.left != nil) ? z.left : z.right;
    child.parent = z.parent;                         // 唯一的孩子顶替 z 的位置
    if (z.parent == nil) {
        root = child;
    } else if (z == z.parent.left) {
        z.parent.left = child;
    } else {
        z.parent.right = child;
    }
    if (z.color == BLACK) {
        fixAfterDeletion(child);                     // 被删节点为黑:黑高被破坏,进入双黑修复
    } else {
        // 被删节点为红:摘除不影响任何路径的黑节点数,性质 5 保持,无需调整
    }
}

修复的目标是把 child(它现在"缺"一个黑节点)上多出来的黑色传递出去:

private void fixAfterDeletion(RbNode<K, V> x) {
    while (x != root && x.color == BLACK) {          // 双黑状态只在此条件下存在
        if (x == x.parent.left) {
            RbNode<K, V> s = x.parent.right;         // 兄弟
            if (s.color == RED) {                    // 情形 1:兄弟为红
                s.color = BLACK;
                x.parent.color = RED;
                rotateLeft(x.parent);
                s = x.parent.right;                  // 兄弟已变,需重取
            }
            if (s.left.color == BLACK && s.right.color == BLACK) {
                s.color = RED;                       // 情形 2:两侄全黑,黑色上移
                x = x.parent;
            } else {
                if (s.right.color == BLACK) {        // 情形 3:远侄为黑,先转为情形 4
                    s.left.color = BLACK;
                    s.color = RED;
                    rotateRight(s);
                    s = x.parent.right;
                }
                s.color = x.parent.color;            // 情形 4:远侄为红,染色后旋转
                x.parent.color = BLACK;
                s.right.color = BLACK;
                rotateLeft(x.parent);
                x = root;                            // 修复完成,跳出循环
            }
        } else {
            // x 是右孩子:左右对称,rotateLeft 与 rotateRight 互换
        }
    }
    x.color = BLACK;                                 // 结束时把 x 染黑(含 x 为根的情形)
}

与插入框架的对照:

特征 插入调整 删除调整
循环条件 父节点为红(违反性质 4) 当前节点非根且为黑(双黑状态)
循环内的"当前节点" 冲突位置,向根方向上移 缺黑位置,向根方向上移
会传播的情形 情形 1(变色) 情形 2(变色)
结束条件 情形 3 完成后自然结束 情形 4 完成后置 x = root,或当前节点变红/变根
旋转次数 至多 2 次 至多 3 次

最后一行 x.color = BLACK 承担两种情形:一是循环因 x 为红而退出,把红染黑即补上缺失的黑;二是循环因 x 为根而退出,把根染黑使整棵树的黑高统一。

2.4 验证红黑性质的检查方法

红黑树的缺陷往往在特定操作序列下才暴露,因此校验函数应在开发与测试阶段每次操作后自动调用。递归校验可以同时检查全部五条性质与有序性,做法是让递归返回子树的黑高:

// 返回以 n 为根的子树的黑高(含哨兵),同时校验性质 3、4、5 与有序性
private int check(RbNode<K, V> n, RbNode<K, V> parent, K lo, K hi) {
    if (n == nil) {
        return 1;                                          // 性质 3:哨兵为黑,贡献 1
    }
    if (n.color == RED && parent != null && parent.color == RED) {
        throw new IllegalStateException("违反性质 4:连续红节点 " + parent.key + " → " + n.key);
    }
    if (lo != null && compare(n.key, lo) <= 0) {
        throw new IllegalStateException("左界失序:" + n.key + " 应大于 " + lo);
    }
    if (hi != null && compare(n.key, hi) >= 0) {
        throw new IllegalStateException("右界失序:" + n.key + " 应小于 " + hi);
    }
    int lh = check(n.left, n, lo, n.key);
    int rh = check(n.right, n, n.key, hi);
    if (lh != rh) {
        throw new IllegalStateException("违反性质 5:节点 " + n.key
                + " 的左右黑高不一致 " + lh + " 与 " + rh);
    }
    return lh + (n.color == BLACK ? 1 : 0);
}

private void checkTree() {
    if (root.color != BLACK) {                              // 性质 2
        throw new IllegalStateException("违反性质 2:根不是黑色");
    }
    check(root, null, null, null);
}

这一实现有一处设计要点:黑高由递归返回值累加,而不是存放在节点字段里。红黑树的节点通常不保存黑高(否则就与 AVL 的高度字段一样需要维护),校验时必须现算。返回值口径是"含哨兵的黑节点数",因此哨兵返回 1 而不是 0,使"叶子为黑"这一性质自然并入计数。

校验覆盖的五项:

校验项 检查方式
性质 1(非红即黑) 由布尔类型在编译期保证,不需要运行期检查
性质 2(根为黑) 单独判断 root.color
性质 3(叶子为黑) 递归在 n == nil 时返回 1,把哨兵计入黑高
性质 4(无连续红) 向下递归时把父节点作为参数传入
性质 5(黑高一致) 比较左右递归返回值
有序性 递归时传入键的开区间下界与上界(比中序校验更早定位出错位置)

有序性的另一种校验方式是中序遍历收集全部键并检查是否升序,实现更简单且不需要传入边界,缺点是只能报告"存在失序"而无法定位到具体节点。两种方式可以并用:中序校验作为快速检查,边界校验作为定位手段。

2.5 与 AVL 实现的结构差异

两份实现对照,可以看清两种平衡策略在代码组织上的分工:

维度 AVL 红黑树
节点附加信息 高度(整数字段) 颜色(1 位)
是否需要父指针 不需要(旋转返回新子树根) 需要(插入删除的修复要向根方向走,且需要判读叔叔与兄弟)
调整的方向 自底向上回溯,依赖递归返回 自底向上,依赖父指针或递归返回
修复的判读依据 平衡因子 父与叔的颜色
最难的函数 delete(级联旋转与高度判断) fixAfterDeletion(四种情形的转换)
校验函数返回 子树高度 子树黑高

两处相同的地方值得强调:旋转函数的指针改写顺序与高度/颜色的更新顺序完全一致(先接管子树、再改写父子、先更新下层、再更新上层),且两者都必须把旋转后的子树根接回父节点(返回根或改写 parent 的对应孩子)。

3. 复杂度与实测

3.1 复杂度与旋转次数对照

操作 AVL 树 红黑树 说明
查找 O(log n),树高上界 1.44 log₂n O(log n),树高上界 2 log₂(n+1) 比较次数等于路径长度
插入 O(log n) O(log n) 定位 O(log n) 加常数次结构调整
删除 O(log n) O(log n) 同上
求最值、前驱、后继、取整 O(log n) O(log n) 沿路径,必要时回溯一步
中序有序遍历 O(n) O(n) 与树高无关
插入的结构调整 至多 1 次重构(含双旋至多 2 次单旋) 至多 2 次旋转
删除的结构调整 至多 O(log n) 次重构 至多 3 次旋转 差异最明显的两项
每次更新沿路径的字段写 高度更新 O(log n) 次 变色 O(log n) 次 两者都有,但都是简单字段写
空间 O(n),每节点 1 个高度字段 O(n),每节点 1 位颜色 均不含键值

表中的 O(log n) 都是最坏情况(不是期望),这是平衡树相对于跳表的核心优势。AVL 的"删除至多 O(log n) 次重构"与红黑树的"删除至多 3 次旋转"是两者最重要的量化差别,其来源已在第二章 2.4 节与 3.4 节说明。

3.2 实测比较的设计

树高上界之比是常数 1.39,意味着单次操作的比较次数差距在常数级别,加上缓存行为与比较代价的干扰,两类树的实际性能差异必须通过实测判断。设计对比基准时的注意事项,与跳表一章的实测部分相同,方法层面的完整说明见 JMH 微基准测试 第 3.4 节与第 3.5 节。

维度 设计要点
规模参数化 至少覆盖 10³、10⁵、10⁷ 三个点,观察耗时随规模变化的曲线形态,而非比较单点数值
操作混合 纯查找、查找与插入各半、含删除的更新流分别测量;删除占比单独参数化,因为这是两类树差异最大的操作
键的分布 随机键与递增键分别测量。顺序输入下 AVL 的树高会接近上界,红黑树的旋转与变色次数也会上升,两者的响应不同
键的类型 整数键与字符串键分别测量;字符串比较的代价可能主导整体耗时,抵消树高差异
对照实现 以标准库的有序映射(如 TreeMap)作为基准,避免把"实现质量差异"误读为"结构差异"
结果消费 用黑洞消费查找结果,避免查找被即时编译整体消除
预热与隔离 分叉进程隔离、固定预热轮次、固定堆与 GC 参数
记录分配量 除时间外记录每次操作的分配字节数;自行实现的节点分配次数与标准库可能不同
校验开关 若实现中包含每次操作后的不变量校验,实测时必须关闭,否则测到的是校验函数的耗时

关于结果表述,需要遵守与跳表一章相同的口径:结论必须带条件(规模、分布、JDK 版本、堆参数),不得无条件外推。可以给出的、不依赖具体数值的结论只有三条:

  1. 查找路径上 AVL 的平均比较次数少于红黑树,因为树高上界低约 30%,且在相同的键集合下 AVL 的高度也更小。
  2. 更新路径上红黑树的旋转次数少于 AVL,尤其在删除占比高的负载中;AVL 的删除旋转次数随树高增长。
  3. 两者的差距在量级之外,实际差距需要按上表设计基准测量,并且可能被键的比较代价与缓存行为覆盖。

3.3 复杂度结论的表述边界

三点容易混淆的地方需要明确:

  1. "O(log n)"不区分 AVL 与红黑树。上界的系数差别(1.44 与 2)在渐近记号中被吸收,只有实测或最坏比较次数的精确计算才能体现。这与复杂度分析中"相同量级必须实测"的一般结论一致(见 复杂度与算法分析 第 2.7 节)。
  2. "旋转次数为常数"与"调整代价为常数"不是一回事。红黑树的插入旋转次数上界为 2,但变色可能沿路径传播 O(log n) 次;每次变色是一次字段写,代价很小但不能说"调整代价为常数"。
  3. AVL 的删除旋转上界 O(log n) 是紧的,不是悲观估计:构造一条路径使每个祖先的较高侧孩子平衡因子都为 ±1,即可让每个祖先都触发旋转。这与插入的"至多一次"形成鲜明对比。

4. 应用与观察

4.1 标准库有序容器的使用要点

以 Java 的 TreeMap 为例,使用中需要明确的语义边界:

要点 说明
用比较判等,不用 equals TreeMap 以 compare 的结果为 0 判定"同一个键"。若比较器与 equals 不一致(如按字符串长度比较),两个 equals 为 false 的键会互相覆盖
键必须可比较 既未实现 Comparable、构造时也未传 Comparator,第一次 put 抛 ClassCastException
键在作键期间不可变 修改参与比较的字段会使元素"失联",与散列表的键不可变要求同源(见 散列表 第 5.2 节)
非线程安全 并发有序访问应使用 ConcurrentSkipListMap,而非给 TreeMap 加锁(见 Java 并发编程)
范围方法是视图 headMap、tailMap、subMap 返回原映射的视图,对视图的修改作用于原映射,且原映射结构变化后视图失效
迭代顺序为键序 与 HashMap 的不可预测顺序不同,TreeMap 的迭代顺序由比较器决定,可以依赖
导航方法都在 O(log n) ceilingKey、floorKey、higherKey、lowerKey、firstKey、lastKey 及带 Entry 的变体
序列化与克隆会复制结构 复制一棵 n 个节点的树为 O(n),与列表的复制同量级

TreeSet 是 TreeMap 的薄封装,上述语义全部继承(见 Java 集合框架实现原理 第 5.3 节的 Set 实现对照)。

4.2 需要自定义平衡树的场景

标准库未覆盖的能力有四类,此时自行实现或在标准库之上补一层结构是必要的:

  1. 按排名访问。给定元素求名次、给定名次求元素,需要在每个节点维护子树规模字段,并在旋转时同步修正参与旋转的两个节点的规模:
旋转前:size(y) = 1 + size(x) + size(T3)      (以右旋为例,x 是 y 的左孩子)
旋转后:size(y) = 1 + size(T2) + size(T3)
        size(x) = 1 + size(T1) + size(y)

更新顺序与高度字段完全一致:先更新降下去的节点,再更新升上去的节点。TreeMap 不提供排名接口,正是因为默认不维护这一字段(对照见 跳表 第 2.5.2 节,跳表用 span 字段原生支持排名)。

  1. 区间聚合。在节点上维护子树的聚合值(区间和、最大值、最小值、元素计数),旋转时用子节点的聚合值重算。这一类结构常称为"伸展树式的区间树"或"树状数组的树形替代",适合需要在线区间统计的场景。维护聚合值与维护规模字段的模式完全一致。

  2. 持久化或函数式结构。要求在修改时保留旧版本(版本比对、撤销重做、并发读快照),需要路径复制:每次操作只复制从根到修改位置的那条路径上的节点,未改动的子树共享。二叉平衡树配合路径复制可以得到 O(log n) 的版本创建代价;跳表也能做,但路径更长、复制量更大。

  3. 交错使用标准库无法表达的比较语义。例如需要按键的多个字段以不同优先级排序、需要在比较器中访问外部状态、需要"比较结果为 0 但元素不相等"的多重集合语义。这类需求可以在标准库之上用"复合键"或"键加序号"的方式绕开,只有当语义确实无法表达时才需要自行实现。

不属于必要场景的几类需求:只是想"更快"、想"避免装箱"、想"减少内存"。这三类需求在两个量级相同的实现之间的收益需要实测确认,而自行实现引入的缺陷风险通常高于收益。

4.3 调试平衡树的方法

平衡树的缺陷具有一个共同特征:结构破坏后,错误往往不在出错的代码行暴露,而在后续某次操作中才以异常结果出现。因此调试手段的关键是"缩小出错的操作范围",而不是"检查出错的那一行"。可用的手段按成本从低到高排列如下。

手段一:中序校验。 中序遍历收集全部键,检查是否严格升序。这可以立即区分两类错误:

  • 中序失序 → 旋转的方向、指针的接管顺序写错了;
  • 中序有序但结果异常 → 旋转正确,是高度字段、平衡因子或颜色判读出错。
def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.key)
    inorder(node.right, out)

手段二:不变量校验。 递归重算子树的高度(AVL)或黑高(红黑树),与字段值及兄弟之间的差值比对。AVL 的校验在第二章 1.3 节的"保存高度"做法下非常直接:

def check_avl(node):
    """返回子树高度,同时校验平衡因子与高度字段的一致性。"""
    if node is None:
        return 0
    lh = check_avl(node.left)
    rh = check_avl(node.right)
    if abs(lh - rh) > 1:
        raise AssertionError(f"平衡因子越界:{node.key} 左 {lh} 右 {rh}")
    if node.height != 1 + max(lh, rh):
        raise AssertionError(f"高度字段未同步:{node.key} "
                             f"字段 {node.height} 实际 {1 + max(lh, rh)}")
    return node.height

红黑树的校验见 2.4 节。校验函数应在测试环境中每次操作后调用,配合随机操作序列(随机插入、删除、查找数万次),可以在几秒内覆盖大量边界组合。这是发现红黑树删除缺陷最有效的方式。

手段三:规模与结构校验。 检查节点总数是否等于"1 加左右子树规模之和",以及树高是否落在上界之内:

def check_size(node):
    if node is None:
        return 0
    n = 1 + check_size(node.left) + check_size(node.right)
    if node.size != n:
        raise AssertionError(f"规模字段未同步:{node.key}")
    return n

def check_height(node):          # 仅对 AVL 有效,返回树高
    return check_avl(node)

树高校验的意义在于发现"平衡条件的实现被绕过":所有局部判断都通过,但整体高度超标,说明某处旋转没有真正改变高度,或某处回溯被提前终止。

手段四:可视化输出。 括号表示法是最省事的可视化方式,一次打印即可看出形状:

def dump(node):
    """括号表示法:左子树、键、右子树;空子树输出为点。"""
    if node is None:
        return "."
    return "(" + dump(node.left) + " " + str(node.key) + " " + dump(node.right) + ")"

某一棵合法 AVL 树可能输出为:

((. 1 .) 2 ((. 4 .) 5 (. 7 .)))

        2
       / \
      1   5
         / \
        4   7

需要更直观的图形时,可以输出 Graphviz 的 DOT 格式并渲染,颜色字段直接映射为节点颜色,这对红黑树的着色错误尤为有效。

手段五:与标准库对照。 用同一批操作(相同顺序的插入、删除、查找)分别作用于自行实现的结构与 TreeMap,比较每一步的结果与最终的中序序列。这是成本最低的差分测试:两边的接口不同,但中序序列与查找结果应当完全一致。

5. 常见问题与排查

现象 可能原因 验证与处置
中序失序,查找结果随机错误 旋转方向写反(LL 用了左旋、RR 用了右旋),或双旋的两步顺序颠倒 用中序校验确认失序;核对"左重右旋、右重左旋"以及双旋"先内后外"的第一步方向;对照第二章 2.2 节的四种图示逐个检查指针
结构看似平衡,但出现空指针异常或数据丢失 旋转时只更新了一个方向的指针,或漏掉子树根的接回 逐个比对旋转代码的指针改写条数与图示(一次单旋涉及 3 条子树指针);检查调用处是否把返回值接回父节点(node.left = rotateLeft(node.left))
插入后某次操作开始出错,此前一直正常 高度字段或平衡因子在旋转后未更新,或更新顺序颠倒 打开每次操作后的不变量校验;重点检查 updateHeight 是否在旋转函数内部的正确位置调用,且顺序为"先降后升"
删除后树仍然"看起来正常",但高度或黑高被破坏 删除后不变量未恢复:AVL 提前终止了回溯,或红黑树的修复循环被提前跳出 对 AVL,检查 rebalance 是否在每一层递归返回前都被调用;对红黑树,检查 fixAfterDeletion 的循环是否只在 x == root 或 x.color == RED 时退出,以及情形 4 是否把 x 置为根
红黑树某次插入后出现连续红节点 情形 1 的"上移"漏掉了把祖父作为新的当前节点,或情形 3 的染色在旋转之后执行(染色对象已失效) 校验函数会直接报出连续红节点的位置;检查情形 1 的末尾是否执行 z = g,情形 3 的染色是否在旋转前完成
红黑树删除时偶发"兄弟为空"或空指针异常 使用了哨兵但删除时把哨兵从树中摘除,或未使用哨兵却漏了空值判断 确认哨兵是共享实例、永不被摘除;检查 child 为哨兵时 child.parent 的赋值是否指向了正确的父节点
递归实现与迭代实现混用后状态不一致 同一棵树同时存在"父指针"与"递归返回子树根"两种维护方式,二者对同一结构的更新互相覆盖 选定一种实现方式:递归返回子树根则不需要父指针;使用父指针则不通过返回值改写结构。混用时至少要保证"父指针的维护"与"返回值的接回"不产生两条相互独立的状态流
调用方修改键后元素失联 键在作键期间被修改,破坏了比较语义 键不可变;更新实现为"按键删除再加新键插入"。与散列表的键不可变要求一致
树的节点数、规模字段与实际不符 删除时遗漏了规模字段的递减,或旋转时只更新了一个节点的规模 用规模校验逐节点比对;核对旋转中规模的重算顺序是否为"先降后升"
键的比较结果为 0 却被当作两个不同的键 使用标准库的有序映射时,误以为它按 equals 判等 统一以比较结果为判定依据;若语义上需要"比较相等但元素不同",改用多重映射或用复合键扩展比较器

排查顺序建议。 平衡树的缺陷排查应先把"结构层"与"字段层"分开:

  1. 先跑中序校验。失序说明旋转的指针改写有错,问题在旋转函数或调用处。
  2. 中序有序但行为异常,跑不变量校验。校验失败会直接指出出错节点与具体不变量,据此定位是插入还是删除的修复路径。
  3. 两项校验都通过时,问题可能在字段之外:比较器语义、键的可变性、迭代过程中的结构修改(对应集合框架的 modCount 机制,见 Java 集合框架实现原理 第 6.2 节)。
  4. 校验函数本身可能写得比被测代码更宽松(例如只检查了局部的平衡因子而没有重算高度)。校验失败的缺失不足以证明实现正确,此时改用手段五的差分测试,与标准库逐操作对照。

6. 检查清单

6.1 实现层面的自检项

旋转:

  • 单旋的指针改写条数是否与图示一致(一次单旋改写 3 条子树指针加 2 条父子关系)?
  • 旋转前是否已保存了需要接管的子树(t2),避免后续读取到已被覆盖的指针?
  • 高度或颜色字段的更新顺序是否为"先降后升"?
  • 旋转函数是否返回了新的子树根,调用处是否把返回值接回原位?
  • 双旋的第一步是否把返回值接回失衡节点的孩子字段(node.left = rotateLeft(node.left))?
  • 左旋与右旋的实现是否严格镜像(把一处的 left 全换成 right 后应当一致)?

插入:

  • 键已存在时的处理是否明确(更新载荷、累加计数或拒绝)?
  • 空树的插入是否绕过 rebalance?
  • AVL 的 rebalance 是否位于递归返回前、且每层都调用?
  • 红黑树的新节点是否染红?循环结束后是否把根染黑?
  • 红黑树的情形 2 之后是否重取了父节点引用?
  • 红黑树的情形 3 的染色是否发生在旋转之前?

删除:

  • 两个孩子的节点是否按后继替换内容,并转为删除后继?
  • 后继是否可能为 null(右子树为空)时已先行处理?
  • AVL 的删除是否在每一层回溯都执行了 updateHeight 与 rebalance?
  • 红黑树删除修复的循环条件是否为"当前节点非根且为黑"?退出后是否把当前节点染黑?
  • 删除修复中的情形 1 与情形 3 之后是否重取了兄弟引用?

校验与测试:

  • 是否实现了中序校验与不变量校验,并在测试环境的每次操作后调用?
  • 是否用随机操作序列(插入、删除、查找混合)做了长时间测试?
  • 是否与标准库的有序映射做了逐操作差分对照?
  • 校验函数是否覆盖了"键的边界"(最小键、最大键、单节点树、空树)?

6.2 何时不该自己实现

判据 结论
需要的操作在标准库有序容器中都有 直接使用标准库,不自行实现
只需要有序遍历与范围、邻近查询 标准库的 TreeMap 与 TreeSet 已覆盖
需要并发有序访问 使用跳表实现的并发容器,而非自行给平衡树加锁
只需要按排名或区间聚合,且没有其他约束 先评估跳表的 span 字段能否直接满足(见 跳表 第 2.5.2 节)
数据静态、构造后不改动 有序数组加二分,空间与缓存表现更好
主要代价来自磁盘或闪存的块访问 使用多叉平衡树(B+ 树),二叉平衡树不适用
已有实现能满足功能,只是"想更快" 先实测确认瓶颈,再考虑替换;同类量级实现的差异通常由键的比较代价与缓存行为决定
确有标准库无法表达的需求(排名、聚合、持久化、特殊比较语义) 自行实现,并按下表配置校验与测试

自行实现时的最小要求:

  1. 覆盖中序校验与不变量校验两个函数,并在测试环境默认开启。
  2. 用随机操作序列与标准库做差分对照。
  3. 在代码注释中标明每个旋转函数的"输入形状、输出形状、高度变化",使后续维护者可以按图示核对。
  4. 实现完成后用微基准实测(方法见 JMH 微基准测试),确认收益存在且可复现。

四、总结

问题与解法。 二叉搜索树的查找代价等于树高,随机插入顺序下为期望 O(log n),但按键有序插入会让树退化为链,代价回到 O(n),且这一输入可以由外部构造。平衡树的解法是在不改变键序的前提下维护一条结构不变量,把树高限制在对数级;实现手段是旋转——它交换相邻节点的父子关系,中序序列完全不变,因此可以任意施加而不影响有序性。完全平衡的维护代价过高,实际采用的是近似平衡:AVL 把约束加在高度差上,红黑树把约束加在颜色上。

树高的推导。 高度为 h 的 AVL 树最少节点数满足 N(h) = N(h−1) + N(h−2) + 1,解为 N(h) = F(h+2) − 1,由此得到树高上界约 1.44 log₂(n + 1) − 0.33,即 1.44 log₂n。红黑树的树高上界由性质 4 与性质 5 导出:黑高为 bh 时最短路径长度为 bh、最长路径不超过 2bh,因此最长路径不超过最短路径的两倍;再由 n ≥ 2^bh − 1 得到 h ≤ 2 log₂(n + 1)。两者的上界之比约为 1.39。判定失衡的依据是平衡因子(保存高度)或颜色(红黑树,无需高度)。

AVL 的机制。 不变量是每个节点的平衡因子属于 {−1, 0, +1}。失衡有 LL、RR、LR、RL 四种形态:前两者用一次单旋,后两者先用一次旋转转为前两者中的一种再修复。插入时沿路径回溯,第一次触发旋转的节点就是最高的一处失衡点,旋转后子树高度恢复到插入前的值,因此回溯可以立即终止——插入至多一次重构。删除的子树高度可能减少 1,旋转不足以恢复祖先的高度,因此可能沿路径级联,删除的旋转次数上界为 O(log n);唯一的例外是失衡节点的较高侧孩子平衡因子为 0,此时旋转后高度不变,可以提前终止。

红黑树的机制。 五条性质(节点非红即黑、根为黑、叶子为黑、无连续红节点、黑高相同)中,后两条是全部结论的来源。把红黑树视为 2-3-4 树的二叉表示后,规则变得可解释:黑节点与其红孩子合起来代表 2-3-4 树的一个多键节点,性质 4 对应节点最多容纳 3 个键,性质 5 对应所有叶子等深。插入分三种情形(叔为红则变色并上移、叔为黑且当前节点在内侧则先旋转、叔为黑且在外侧则染色后旋转),旋转次数不超过 2 次,变色次数可能为 O(log n)。删除需要先归约为"删除至多有一个孩子的节点",若被删节点为黑则进入双黑修复,四种情形(兄弟为红、两侄全黑、远侄为黑、远侄为红)中情形 2 会向上传播,旋转次数不超过 3 次。

对比与选择。 两种树的树高都是 O(log n),差别落在系数与调整量上:AVL 查找更优(树高上界低约 30%),红黑树更新更优(删除旋转次数从 O(log n) 降到常数 3)。读多写少、删除占比低、需要更紧的树高上界时选 AVL;读写混合、删除占比高、复用标准库时选红黑树。两者的实现复杂度不对称:AVL 的插入较短,红黑树的删除最难。量级相同意味着最终取舍必须实测,且结论要带规模、分布与版本等条件。

其他平衡结构。 Treap 用与键无关的随机优先级替代平衡条件,形状与随机插入顺序的 BST 分布相同,支持 O(log n) 的分裂与合并;替罪羊树用规模约束加事后重建替代持续旋转,摊还 O(log n);Splay 树每次访问把节点伸展到根,摊还 O(log n) 并利用访问局部性,但单次操作无最坏保证且读操作也改结构;跳表用随机层数实现概率平衡,最坏 O(n)、期望 O(log n),优势在实现简单与并发友好。多叉平衡树把树高换成扇出,把 10⁸ 级数据的树高压到 3 至 4 层,因此成为磁盘索引的默认结构;在内存中,节点大小超过缓存行时页内查找的额外成本会抵消树高降低的收益,二叉结构仍然是主流。

工程落点。 标准库的有序映射与有序集合(TreeMap、TreeSet、std::map、std::set、Linux 内核 rbtree)基本都采用红黑树,选择理由是最坏情况下更新代价更优、额外空间只需一个颜色位。第二处落点是散列表的桶内树化:HashMap 在桶内节点数达到 8 且表容量不小于 64 时转为红黑树、降到 6 时退化回链表,树化是防御性兜底而非默认路径。多数业务代码无需自行实现平衡树:标准库已覆盖有序遍历、范围查询与邻近查询,而手写实现的正确性成本极高、性能收益通常不存在。

实现与排查。 旋转的代码有三条固定要求:先接管子树再改写父子、先更新下层再更新上层、把新的子树根接回原位。AVL 在节点保存高度,红黑树用哨兵统一空位并需要父指针。校验是调试平衡树的主要手段:中序校验区分"指针写错"与"字段写错",不变量校验(AVL 的平衡因子与高度一致性、红黑树的连续红与黑高一致)直接指出出错节点,规模校验与括号表示法的可视化用于定位结构性偏差。常见缺陷集中在五处:旋转方向写反、只更新一个方向的指针、删除后不变量未恢复、平衡因子或颜色字段未同步、递归与迭代实现混用导致状态不一致。是否自行实现,判据只有一条——标准库无法表达所需操作时才实现,且必须配上每次操作后的校验与与标准库的差分测试。