平衡树是在二叉搜索树的基础上,通过维护结构不变量把树高限制在对数级的存储结构。本文讨论 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),与顺序扫描有序链表没有区别,但每个节点还多付出了两个指针的空间代价——结构变差了,代价却更高。
退化并非罕见输入造成的意外。以下都属常见来源:
- 键本身有序。按时间递增的日志、自增主键、按文件路径排序的目录项,读入顺序天然有序。
- 批量导入。从数据库按主键顺序
ORDER BY取出一批记录再逐条插入,顺序已定。 - 外部可控的输入。键来自请求参数或用户上传的数据时,攻击者可以构造出让结构退化的插入顺序,这与散列表被恶意构造哈希碰撞属于同一类问题(见 散列表 的哈希攻击一节)。
结果是: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 保证同一节点的所有下行路径黑高相同。于是有两条结论:
- 最短路径长度等于黑高。全由黑节点构成的路径是最短的,其长度为 bh(此处长度按节点数计,含叶子)。
- 最长路径长度不超过两倍黑高。性质 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 树高之外的成本
树高决定比较次数,但操作的实际耗时还取决于另外两项,二者都不由树高决定:
- 每层下降对应一次指针跳转与一次缓存访问。节点在堆上离散分配,树越高,跳转次数越多,缓存未命中的概率越大。这一项的系数与节点大小、分配器的排布有关,与树高同阶但难以解析计算。
- 每次比较的代价。整数键的比较是一条指令,字符串键的比较是一次可能跨越多个缓存行的内存扫描。键的比较代价高时,树高从 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 节的结论提炼出来,可以得到旋转操作的三条性质,它们构成了所有平衡树实现与调试的基础:
- 中序序列不变。旋转不跨越任何键的相对次序,因此有序性自动保持,无需任何额外的比较或重排。
- 只改动常数个指针。一次旋转涉及 2 个节点的父子关系与 3 条子树指针,代价与树规模无关。
- 树高变化可预测。旋转后子树的高度要么不变,要么减少 1,因此是否继续向上修复可以精确判断(2.4 节的表格就是这一判断的量化)。
这三条性质使旋转成为"局部可逆的塑形操作":正确的旋转序列无论怎样组合,都不会破坏有序性;而错误的旋转(方向写反、指针漏改)会立即破坏有序性或高度字段的一致性,因此在调试中表现为两种可检测的症状(见第三章第 4 节与第 5 节)。
3. 红黑树
红黑树(Red-Black Tree)由 Guibas 与 Sedgewick 在 1978 年提出,用颜色而非高度来表达平衡约束。它的平衡条件不如 AVL 直观,但换来了两个结果:旋转次数为常数,以及可以用一个颜色位表达全部平衡状态。
3.1 五条性质及其含义
红黑树在二叉搜索树上附加五条性质:
- 每个节点是红色或黑色。颜色是节点的唯一附加信息,一个二进制位。
- 根节点是黑色。
- 每个叶子节点(NIL,空指针所指向的哨兵)是黑色。(若实现中不设哨兵而直接用
null表示空,则约定空指针视为黑。) - 红色节点的两个子节点都是黑色,即不存在父红子红这样的连续红节点。
- 从任一节点出发到其所有叶子的路径上,黑节点数目相同,即同一节点的黑高唯一。
五条性质的作用可以逐条对应到结构上:
| 性质 | 直接作用 |
|---|---|
| 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 个键却还要被删除,节点会变成空),需要向兄弟节点"借"一个键(对应红黑树的旋转与变色),或与兄弟合并(对应红黑树的变色上移)。这一组操作比插入复杂,是红黑树删除实现困难的根源。
这一等价关系带来两个实用推论:
- 可以把红黑树的调整逻辑理解为"在 2-3-4 树上做局部修正",从而减少对五条性质的逐条背诵。凡是"需要分裂"或"需要借键"的时刻,红黑树中必然出现一次变色或旋转。
- 不同的等价方式导出不同的红黑树变体。上表描述的是经典 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 次比较 |
两点工程含义:
- 绝对差值是"最坏情况下的比较次数差",不是平均差。红黑树的平均路径长度明显短于上界(随机键的平均深度约为 2 log₂n 量级中的较低值),实测差距通常小于上表的差值。这与复杂度分析中"上界不等于实际值"的一般情形一致(见 复杂度与算法分析 第 2.3 节)。
- 即使按最坏情况计,差值也是常数级别。两类树的树高都是 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 形状"分布相同。
由此得到两条结论:
- 期望树高为 O(log n),与随机插入顺序的 BST 期望树高一致;无需维护任何平衡因子或颜色。
- 不存在能构造出退化输入的键序列,因为形状由随机优先级决定,与键的取值和插入顺序无关。这一点与跳表相同(见 跳表 第 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 节,桶内结构的对照见 散列表 的哈希攻击与防护一节。
这里有三点与本文直接相关:
- 为什么选红黑树而不是 AVL。桶内结构的访问模式以"插入与删除交替"为主(哈希表的增删频繁),AVL 删除的级联旋转在这个场景下代价偏高;红黑树的删除旋转次数为常数,更适合。同时红黑树只需一个颜色位,而
HashMap的桶节点还需要承载链表顺序与扩容拆分的额外指针,内存本就紧张。 - 为什么桶内结构的树化在容量不足时被推迟。容量小于 64 时冲突的根因是表太短,扩容摊开元素比在短表上维持红黑树更划算。这与 4.1 节的结论一致:平衡树解决的是"在同一批元素上维持对数级深度",而扩容解决的是"元素是否放错了位置"。
- 树化节点比链表节点大得多。
HashMap.Node约 32 字节,树化后的TreeNode约 48 字节(多出左右子指针、父指针与颜色位)。因此树化是兜底而非默认:正常散列分布下绝大多数桶只有 0 至 2 个节点,不会进入树化分支。
6.3 为什么多数业务代码无需手写
综合以上,自行实现平衡树的必要性很低,理由是:
- 标准库的接口已经覆盖常见需求。有序遍历、范围查询(
headMap、tailMap、subMap)、邻近查询(ceilingKey、floorKey、higherKey、lowerKey)、最值查询(firstKey、lastKey)在TreeMap上都是 O(log n)。这些覆盖了有序映射的绝大多数用法。 - 手写实现的正确性成本极高。红黑树的删除涉及双黑修复的四种情形及其转换,任一边界写错都会在特定操作序列下破坏不变量,而这类错误往往不在常规用例中暴露(见第三章第 5 节)。
- 性能收益通常不存在。标准库实现经过长期优化,泛型与内联保证了比较与指针操作的常数开销接近手工实现;自行实现的常见后果是把 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;
}
代码结构上有四处固定要求:
- 指针改写顺序固定为"先接管子树,再改写父子"。以上例为例,
t2必须在x.right = y之前或之后取到,且必须在y.left = t2之前取出。若先执行x.right = y再取x.right,取到的是y而非原来的t2,结构即刻被破坏。 - 高度更新顺序固定为"先下层后上层"。
y旋转后成为x的孩子,其高度必须先用新的子树重算,x的高度才能基于正确的y.height计算。顺序反了会得到偏大或偏小的高度,进而使平衡因子判读失准。 - 旋转函数返回新的子树根。这是递归实现能够把子树接回父节点的前提,也是避免维护父指针的关键约定。
- 单旋不判断失衡类型。
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); // 可能每个祖先都需要重构
}
三处与插入不同的地方:
- 删除的终止条件不能提前返回。
rebalance返回后必须继续把新的子树根接回上层并让上层继续检查。上述递归写法自然满足这一点——每层调用都在返回前执行updateHeight与rebalance。 - 两个孩子的情形用后继替换内容。这样做避免了父指针的维护,代价是键值被复制一次。若结构上要求节点身份不变(外部持有节点引用),应改为节点替换的写法。
- 删除引发的旋转可能改变子树高度,因此不能像插入那样依赖"高度恢复"来跳过上层。第二章 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);
哨兵的作用有四项:
- 消除空指针判断。判读"叔叔为黑"时,叔叔可能是空位,用哨兵则统一为读取
color字段,不需要uncle == null || uncle.color == BLACK这样的复合条件。 - 使删除修复的边界统一。双黑修复需要判读"兄弟的两个孩子是否为黑",兄弟的孩子常为空位;若用
null,每一处判断都要加空值分支。 - 为黑高提供统一的终点。性质 5 的校验需要一个"黑节点"作为计数终点,哨兵恰好充当这一角色(见 2.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:循环结束后确保根为黑
}
代码框架中的固定要点:
- 循环条件直接表达"违反性质 4"。不需要额外的标志位:只要父节点为红,性质 4 就被破坏,需要修复。
- 情形 2 之后必须重取父节点。
rotateLeft(z)改变了z与p的关系,此后p变量已经过期。这是该实现中最容易出错的细节。 - 情形 3 的染色对象是旋转前的 p 与 g。染色必须发生在旋转之前(或使用旋转前保存的引用),因为旋转会改变
g.parent。 - 循环结束后无条件把根染黑。情形 1 的传播可能一直到根,此时
z为根且为红(由g上移而来),染黑即满足性质 2,且这一步使根的黑高增加 1,性质 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 版本、堆参数),不得无条件外推。可以给出的、不依赖具体数值的结论只有三条:
- 查找路径上 AVL 的平均比较次数少于红黑树,因为树高上界低约 30%,且在相同的键集合下 AVL 的高度也更小。
- 更新路径上红黑树的旋转次数少于 AVL,尤其在删除占比高的负载中;AVL 的删除旋转次数随树高增长。
- 两者的差距在量级之外,实际差距需要按上表设计基准测量,并且可能被键的比较代价与缓存行为覆盖。
3.3 复杂度结论的表述边界
三点容易混淆的地方需要明确:
- "O(log n)"不区分 AVL 与红黑树。上界的系数差别(1.44 与 2)在渐近记号中被吸收,只有实测或最坏比较次数的精确计算才能体现。这与复杂度分析中"相同量级必须实测"的一般结论一致(见 复杂度与算法分析 第 2.7 节)。
- "旋转次数为常数"与"调整代价为常数"不是一回事。红黑树的插入旋转次数上界为 2,但变色可能沿路径传播 O(log n) 次;每次变色是一次字段写,代价很小但不能说"调整代价为常数"。
- 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 需要自定义平衡树的场景
标准库未覆盖的能力有四类,此时自行实现或在标准库之上补一层结构是必要的:
- 按排名访问。给定元素求名次、给定名次求元素,需要在每个节点维护子树规模字段,并在旋转时同步修正参与旋转的两个节点的规模:
旋转前: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 字段原生支持排名)。
-
区间聚合。在节点上维护子树的聚合值(区间和、最大值、最小值、元素计数),旋转时用子节点的聚合值重算。这一类结构常称为"伸展树式的区间树"或"树状数组的树形替代",适合需要在线区间统计的场景。维护聚合值与维护规模字段的模式完全一致。
-
持久化或函数式结构。要求在修改时保留旧版本(版本比对、撤销重做、并发读快照),需要路径复制:每次操作只复制从根到修改位置的那条路径上的节点,未改动的子树共享。二叉平衡树配合路径复制可以得到 O(log n) 的版本创建代价;跳表也能做,但路径更长、复制量更大。
-
交错使用标准库无法表达的比较语义。例如需要按键的多个字段以不同优先级排序、需要在比较器中访问外部状态、需要"比较结果为 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 判等 | 统一以比较结果为判定依据;若语义上需要"比较相等但元素不同",改用多重映射或用复合键扩展比较器 |
排查顺序建议。 平衡树的缺陷排查应先把"结构层"与"字段层"分开:
- 先跑中序校验。失序说明旋转的指针改写有错,问题在旋转函数或调用处。
- 中序有序但行为异常,跑不变量校验。校验失败会直接指出出错节点与具体不变量,据此定位是插入还是删除的修复路径。
- 两项校验都通过时,问题可能在字段之外:比较器语义、键的可变性、迭代过程中的结构修改(对应集合框架的
modCount机制,见 Java 集合框架实现原理 第 6.2 节)。 - 校验函数本身可能写得比被测代码更宽松(例如只检查了局部的平衡因子而没有重算高度)。校验失败的缺失不足以证明实现正确,此时改用手段五的差分测试,与标准库逐操作对照。
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+ 树),二叉平衡树不适用 |
| 已有实现能满足功能,只是"想更快" | 先实测确认瓶颈,再考虑替换;同类量级实现的差异通常由键的比较代价与缓存行为决定 |
| 确有标准库无法表达的需求(排名、聚合、持久化、特殊比较语义) | 自行实现,并按下表配置校验与测试 |
自行实现时的最小要求:
- 覆盖中序校验与不变量校验两个函数,并在测试环境默认开启。
- 用随机操作序列与标准库做差分对照。
- 在代码注释中标明每个旋转函数的"输入形状、输出形状、高度变化",使后续维护者可以按图示核对。
- 实现完成后用微基准实测(方法见 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 的平衡因子与高度一致性、红黑树的连续红与黑高一致)直接指出出错节点,规模校验与括号表示法的可视化用于定位结构性偏差。常见缺陷集中在五处:旋转方向写反、只更新一个方向的指针、删除后不变量未恢复、平衡因子或颜色字段未同步、递归与迭代实现混用导致状态不一致。是否自行实现,判据只有一条——标准库无法表达所需操作时才实现,且必须配上每次操作后的校验与与标准库的差分测试。