红黑树

2026 大纲 六（五）3 红黑树（二叉搜索树见《BST》、平衡二叉树见《AVL 树》）。

教材出处：大纲单列了这一条，但四本主参都没有单列这一节（严蔚敏全书「红黑树」零命中）。成文出处见 殷人昆《数据结构（用面向对象方法与 C++ 描述）》第 2 版 §7.5 红黑树：「红黑树(red-black tree)是这样的一棵二叉搜索树：树中的每一个结点的颜色不是黑色就是红色。可以把一棵红黑树视为一棵扩充二叉树，用外部结点表示空指针。」

为什么在 AVL 之外还要一个红黑树

AVL 树已经把树高限制在 $1.44{\log }_{2}n$ 以内，查找非常快。它的问题出在维护成本：插入至多一次调整、代价可控；但删除可能从删除位置一路旋转到根，最多 $O(\log n)$ 次旋转。

对"查得多、改得少"的场景 AVL 很划算。但对插入删除极其频繁的场景——进程调度队列、内存管理的空闲块表、通用有序容器——每次删除都可能触发连锁旋转，代价就显出来了。

红黑树的做法是放松平衡条件：不要求左右子树高度严格相差不超过 1，只要求某种意义上的"黑色结点数相等"。代价是树可能比 AVL 高出将近一倍，换来的是插入最多转 2 次、删除最多转 3 次。

一句话概括这场交易：红黑树用"查找时多走几层"换"修改时少转几次"。 判断该选谁，就看这两件事在具体场景里哪件更频繁。

五条性质

红黑树是一棵二叉排序树，并且同时满足以下五条：

编号	性质	说明
①	每个结点是红色或黑色	只需 1 bit 额外空间
②	根结点是黑色	—
③	叶结点（NIL）是黑色	这里的"叶结点"指外部的空结点，不是没有孩子的内部结点
④	红结点的两个孩子都是黑色	等价于"不存在两个连续的红结点"，简称不红红
⑤	从任一结点到其所有叶结点（NIL）的路径上，黑色结点数目相同	简称黑高相等

性质 ③ 里的"叶结点"是 NIL 空结点，不是普通的叶子。画树时一定要把 NIL 画出来，否则数黑高必然出错——性质 ⑤ 数的路径终点正是这些 NIL。

        13(黑)
       /      \
     8(红)     17(红)
    /   \       /    \
 NIL   NIL    NIL    NIL       ← 这些才是性质 ③ 说的"叶结点"，全部为黑

黑高 $bh(x)$ 定义为：从 $x$ 出发（不含 $x$ 自己）到任一 NIL 的路径上的黑结点数（NIL 计入）。由性质 ⑤，它与选哪条路径无关。

typedef enum { RED, BLACK } Color;

typedef struct RBNode {
    int key;
    Color color;
    struct RBNode *left, *right, *parent;   // 调整要向上回溯，所以存双亲指针
} RBNode;

性质 ⑤ 不是"左右子树高度相同"。 红黑树完全允许左右子树的实际高度相差很多——只要黑结点数相同、红结点分布不同即可。把它读成"高度平衡"是对红黑树最典型的误解。

先看一眼

加载可视化中...

判定：机械三步

① 根是不是黑色；② 扫一遍红结点，看它的两个孩子（含 NIL）是否都黑；③ 自底向上算黑高——每个结点比较左右子树的黑高，不相等立刻判否，相等则把该结点黑高记为「孩子黑高 $+$ 孩子是否为黑」继续往上。

拿一棵树跑一遍：

              13(黑)
            /        \
        8(红)          17(红)
        /    \         /     \
    1(黑)  11(黑)   15(黑)   25(黑)
       \                     /    \
      6(红)              22(红)   27(红)

第一步：根 13 是黑 ✓ 第二步：红结点有 8、17、6、22、27。8 的孩子 1、11 都是黑 ✓；17 的孩子 15、25 都是黑 ✓；6、22、27 的孩子都是 NIL（黑）✓ 第三步：自底向上算黑高（NIL 黑高为 0）：

结点	颜色	左子树黑高	右子树黑高	是否相等	该结点黑高
6	红	NIL → $0+1=1$	NIL → $0+1=1$	✓	1
1	黑	NIL → 1	6 是红 → $bh(6)+0=1$	✓	1
11	黑	1	1	✓	1
8	红	1 是黑 → $1+1=2$	11 是黑 → $1+1=2$	✓	2
15	黑	1	1	✓	1
25	黑	22 是红 → $1+0=1$	27 是红 → $1$	✓	1
17	红	15 是黑 → $1+1=2$	25 是黑 → $1+1=2$	✓	2
13	黑	8 是红 → $2+0=2$	17 是红 → $2+0=2$	✓	2

三步全过 → 是红黑树 ✓

再验证"最长 $\le$ 2 倍最短"：最短的根到 NIL 路径经过 3 个内部结点，最长的 $13\to 17\to 25\to 22\to \text{NIL}$ 经过 4 个，$4\le 2\times 3$ ✓

三种典型的"不是红黑树"：根是红色（违反 ②）；某红结点的孩子仍是红色（违反 ④）；左子树黑高 2、右子树黑高 3（违反 ⑤）。

两条上界：树高为什么是 $O(\log n)$

结论一：最长路径 $\le$ 2 × 最短路径。 设某结点的黑高为 $bh$。最短的路径全部由黑结点组成，长度为 $bh$；最长的路径红黑交替（性质 ④ 禁止红红相邻，红结点最多占一半且不能连着），黑结点 $bh$ 个、红结点至多 $bh$ 个，总长度至多 $2bh$。故比值不超过 2。

这条结论说明红黑树"歪"是有限度的——虽然不像 AVL 那样左右几乎等高，但两侧的差距永远锁在 2 倍以内。

结论二：含 $n$ 个内部结点的红黑树，$h\le 2{\log }_2(n+1)$。

先证一个引理：以 $x$ 为根的子树至少含 $2^{bh(x)}-1$ 个内部结点。 对 $x$ 的高度归纳：$x$ 是 NIL 时 $bh(x)=0$，子树含 $2^0-1=0$ 个 ✓；$x$ 是内部结点时，它的两个孩子的黑高至少是 $bh(x)-1$（孩子若为黑则恰为 $bh(x)-1$，若为红则仍为 $bh(x)$），由归纳假设每个孩子的子树至少含 $2^{bh(x)-1}-1$ 个，加上 $x$ 自己：

$$2(2^{bh(x)-1}-1)+1=2^{bh(x)}-1$$

主证明：设树高为 $h$。由性质 ④，任一条根到 NIL 的路径上红结点数不超过总数的一半，所以黑结点数至少是 $h/2$，即 $bh(\text{root})\ge h/2$。代入引理：

$$n\ge 2^{bh(\text{root})}-1\ge 2^{h/2}-1⟹h\le 2{\log }_2(n+1)$$

含义：红黑树的高度是 $O(\log n)$，因此查找、插入、删除都是 $O(\log n)$——与 AVL 同量级，只是常数因子大一些（2 对 1.44）。

插入：新结点染红，然后看叔结点

按 BST 规则挂上新结点 → 染红 → 只有双亲也是红色（违反性质 ④）才需要调整；双亲是黑色就什么都不用做。

为什么必须染红：染黑会让该路径黑高 $+1$、必定破坏全局的性质 ⑤，而性质 ⑤ 是全局的，修起来要动整棵树；染红只可能破坏局部的性质 ④（当双亲也是红色时），且能就地变色 / 旋转修复。

设当前结点 $z$、双亲 $P$、祖父 $G$、$P$ 的兄弟（$z$ 的叔结点）$U$。以 $P$ 是 $G$ 的左孩子为例（右孩子完全镜像）：

情形	条件	操作	结果
一	$U$ 为红	$P$、$U$ 染黑，$G$ 染红	不旋转；令 $z=G$ 向上迭代，矛盾上移两层
二	$U$ 为黑，$z$ 与 $P$ 成折线	对 $P$ 旋转（$z$ 是右孩子则左旋）	转成直线，进入情形三
三	$U$ 为黑，$z$ 与 $P$ 成直线	$P$ 染黑、$G$ 染红，对 $G$ 右旋	$P$ 是黑，不会与上层红红，终止

为什么参照物是叔结点：修复思路是把 $P$ 染黑，但这会让 $P$ 这一侧黑高 $+1$ 而破坏性质 ⑤——除非同时把 $U$ 也染黑、把 $G$ 染红。所以能不能用纯变色解决，取决于 $U$ 是不是红的。

情形一：叔结点为红 —— 纯变色，向上迭代

        G(黑)                    G(红) ← 新的 z，继续向上检查
       /    \        变色        /    \
    P(红)   U(红)     ──→     P(黑)  U(黑)
    /                          /
  z(红)                      z(红)

为什么不破坏性质 ⑤：$G$ 以下的每条路径都恰好经过 $P$ 或 $U$ 中的一个，它们各自 $+1$ 个黑，而 $G$ 由黑变红 $-1$ 个黑，净变化为 0 ✓ 这一情形不做旋转，只是把矛盾上移两层，最坏迭代到根。

情形二：叔结点为黑，$z$ 与 $P$ 构成"折线" —— 先转成直线

        G(黑)                     G(黑)
       /    \      对 P 左旋      /    \
    P(红)   U(黑)     ──→      z(红)   U(黑)
       \                       /
       z(红)                 P(红)   ← 交换角色后，P 与 z 成为一条直线

情形三：叔结点为黑，$z$ 与 $P$ 构成"直线" —— 一步终结

$P$ 染黑、$G$ 染红，对 $G$ 右旋。旋转后原来 $G$ 的位置由黑色的 $P$ 顶上，不会与上层红红，调整结束。

旋转次数：情形一不旋转；情形二旋转 1 次后必进入情形三；情形三旋转 1 次后终止——插入最多旋转 2 次，其余是 $O(\log n)$ 次变色上溯。最后统一把根染黑（根由红变黑会让所有路径的黑高同时 $+1$，性质 ⑤ 仍满足）。

情形二、三图里的 $U$ 到底是什么（觉得"$U$ 为黑"不自然时展开）

图里省略了各结点下方挂的子树。$U$ 标成"黑"时有两种可能，别当成"一定挂着一个实体黑结点"：

• $z$ 就是刚插入的叶结点时，$U$ 只能是 NIL（NIL 视为黑）。因为此时 $P$ 是红的、两个孩子原本都是 NIL，$P$ 这一侧的黑高只有 1；$U$ 若是实体黑结点，它自己就贡献 1 个黑、下面还有 NIL，黑高至少 2，性质 ⑤ 当场就不成立了。
• $z$ 是情形一变色上溯上来的内部结点时，$U$ 才可能是有实体的黑结点。

两种来源的旋转与变色步骤完全一样，所以正文统一按一张图讲。

删除：看兄弟，消化"双重黑"

先按 BST 规则删除；两个孩子时转化为删除中序后继，故实际被移除的结点最多只有一个孩子（详见 BST 的删除）。再看它的颜色：

• 移除的是红色结点：不计入黑高、删掉也不产生红红，五条性质全部保持，直接结束；
• 移除的是黑色结点：该位置到叶子的所有路径黑高减 1，破坏性质 ⑤，必须调整。

调整时把缺失的那一重黑色记账在顶替该位置的结点 $x$ 上，称 $x$ 携带"双重黑"，目标就是把它消化掉。设 $w$ 为 $x$ 的兄弟，以 $x$ 是左孩子为例（右孩子对称）：

情形	条件	操作	结果
1	$w$ 是红色	$w$ 染黑、$P$ 染红，对 $P$ 左旋	新兄弟必为黑，转入情形 2 / 3 / 4
2	$w$ 黑，两个侄子都黑	$w$ 染红，双重黑上移给双亲 $P$	$P$ 原为红则染黑即结束；$P$ 为黑则令 $x=P$ 继续迭代
3	$w$ 黑，近侄红、远侄黑	近侄染黑、$w$ 染红，对 $w$ 右旋	新兄弟的远侄变红，转入情形 4
4	$w$ 黑，远侄红	$w$ 取 $P$ 原来的颜色、$P$ 染黑、远侄染黑，对 $P$ 左旋	双重黑被消化，一步终结

为什么删除看兄弟、插入看叔结点：插入是"这一侧多了个红"，要找同层另一半（叔）一起变色；删除是"这一侧少了个黑"，只能从兄弟那侧借。参照物由"缺什么、向谁要"决定。

四种情形各自的道理：

情形 1 不解决问题，只是把"兄弟是红的"这个碍事的情况消掉——旋转后 $x$ 的新兄弟是原来 $w$ 的左孩子，由性质 ④（$w$ 红则孩子必黑）可知它一定是黑色。

情形 2 是唯一会向上迭代的：$x$ 那一侧缺一个黑，就让 $w$ 那一侧也主动少一个黑（$w$ 染红），两侧重新齐平；代价是整棵以 $P$ 为根的子树黑高少了 1，这个亏欠交给上层去补——这正是"上移"的含义。若 $P$ 原本是红色，直接把 $P$ 染黑就吸收掉了；若 $P$ 是黑色，令 $x=P$ 继续向上，最坏迭代到根（此时直接去掉那一重黑，整棵树的黑高减 1，五条性质仍满足）。

情形 3 把"近侄红"转成"远侄红"，为情形 4 铺路。

情形 4 一步终结：左旋后 $x$ 这一侧的路径多经过了一个黑结点 $P$，双重黑被消化；而 $w$ 这一侧原本经过的远侄由红变黑，恰好补上旋转带来的黑高损失；$w$ 继承 $P$ 的颜色则保证更上层看到的黑高完全没变。三处变色一处旋转，各司其职。

"近侄 / 远侄"的定义：以 $x$ 相对于兄弟 $w$ 的方位来说，离 $x$ 近的那个侄子叫近侄、远的叫远侄。$x$ 是左孩子时，$w$ 的左孩子是近侄、右孩子是远侄；$x$ 是右孩子时反过来。这个方位关系在镜像情形下会左右互换，是最容易搞反的一处。

旋转次数：情形 2 不旋转（只变色 $+$ 上移）；情形 1、3、4 各旋转 1 次，最长的转化链是 1 → 3 → 4，所以删除最多旋转 3 次。

删除四种情形的示意图（对照图逐步理解时展开）

情形 1：

       P(黑)                      W(黑)
      /     \       →            /     \
   x(双黑)  W(红)              P(红)    Wr
           /   \              /   \
         Wl     Wr        x(双黑)  Wl

情形 2：

        P(任意色)                   P(双黑或直接染黑)
       /         \       →         /          \
    x(双黑)      W(黑)          x(普通黑)     W(红)
                /   \                        /   \
             Wl(黑) Wr(黑)                Wl(黑) Wr(黑)

情形 3：

        P                      P
       / \                    / \
      x   W(黑)     →        x   Wl(黑)
         /   \                     \
      Wl(红) Wr(黑)                W(红)
                                     \
                                     Wr(黑)

情形 4：

        P(任意色)                    W(取原 P 的颜色)
       /         \       →         /       \
     x(双黑)     W(黑)          P(黑)      Wr(黑)
                /   \           /   \
              Wl    Wr(红)   x(普通黑) Wl

四种情形的转化关系：

情形 1 ──→ 情形 2 / 3 / 4      （消掉"兄弟是红的"）
情形 3 ──→ 情形 4              （把近侄红转成远侄红）
情形 4 ──────────→ 结束        （一步终结）
情形 2 ──→ 上移，最多 O log n 次迭代

与 AVL 的对比，以及与 2-3-4 树的等价

对比项	红黑树	AVL 树
平衡条件	黑高相等（弱平衡）	左右子树高度差 $\le 1$（严格平衡）
最大高度	$2{\log }_2(n+1)$	$1.44{\log }_2(n+2)$
插入的旋转次数	$\le 2$	$\le 2$
删除的旋转次数	$\le 3$，常数	$O(\log n)$，可能连锁
每结点额外空间	1 bit 颜色	一个高度（或 2 bit 平衡因子）
适用场景	插入删除频繁的通用有序容器	查找密集、修改较少

一句话：查得多用 AVL，改得多用红黑树。 两者三个操作都是 $O(\log n)$，真正拉开差距的只有"删除会不会连锁旋转"这一行。

还有一条对照值得知道：红黑树可以等价地转化为一棵 2-3-4 树（即 4 阶 B 树），做法是把每个红结点与它的黑色双亲"合并"成同一个 B 树结点——黑结点带 0 / 1 / 2 个红孩子分别对应 B 树的 2 / 3 / 4 结点。

性质 ⑤（黑高相等）在 B 树那边就是"所有叶结点在同一层"；性质 ④（不红红）保证了合并后每个 B 树结点最多 3 个关键字。 理解了这个对应，红黑树那些看似古怪的调整规则，本质上就是 B 树的结点分裂与合并。

最后提一个容易被忽略的设计意图：旋转次数是常数、变色次数是 $O(\log n)$——旋转要修改多个指针、代价高；变色只改 1 bit、代价极低。红黑树是把昂贵的操作压成常数、把便宜的操作留给 $O(\log n)$。

考点速记

三条会被反复调用的结论：

1. 红黑树的平衡保证来自"不红红"（④）与"黑高相等"（⑤）的合力，由它们直接推出"最长 $\le$ 2 倍最短"与 $h\le 2{\log }_2(n+1)$。
2. 新结点必须染红：染黑必定破坏全局的性质 ⑤，染红最多破坏局部的性质 ④。
3. 旋转次数有常数上界（插入 $\le 2$、删除 $\le 3$），这是它相对 AVL 的唯一实质优势。

这一节至今在 408 真题里不单独成题。 红黑树是较晚才写进大纲的条目（六（五）3），到目前为止还没有出现过直接考它的题——所以下方「真题练习」是空的，这不是漏挂。

不过"没考过"不等于"不用看"，两件事值得留意：

• 它是大纲内条目，随时可能出选择题。 一旦出，最省事的考法就是判定题（给一棵着色的树问是不是红黑树）和性质辨析题（哪条叙述正确）。前者按上面那机械三步走；后者的坑集中在两处——性质 ③ 的"叶结点"指 NIL 不是普通叶子，性质 ⑤ 说的是黑结点数相同、不是高度相同。
• 与 AVL 的对比是更可能被考到的角度。 两者的量级都是 $O(\log n)$，能拉开差距的只有"删除的旋转次数：红黑树是常数、AVL 是 $O(\log n)$"这一条。

复习优先级上，红黑树应排在 BST 与 AVL 之后——那两节年年有题，本节暂时没有。

易错：把性质 ⑤ 读成"左右子树高度相同"。 红黑树允许左右实际高度相差近一倍。

易错：数黑高时不画 NIL。 性质 ⑤ 的路径终点正是这些 NIL，不画必然数错。

易错：把插入的参照物记成兄弟、删除的记成叔结点。 插入看叔、删除看兄。

教材出处

• 红黑树建立在二叉排序树之上，其定义（三条性质与"中序遍历得到递增有序序列"）：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p198（7.3.1 节）
• 引入平衡机制的动机（"二叉排序树查找算法的性能取决于二叉树的结构……如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为 $O(n)$……事实上，树的高度越小，查找速度越快"）：印刷 p205（7.3.2 节）
• 4 阶 B 树（2-3-4 树）的定义，用于理解本篇的等价关系：印刷 p210（7.3.3 节）

说明：严蔚敏这本教材没有红黑树章节（红黑树是较晚才进入大纲的内容），因此本篇的五条性质、黑高、两条上界的证明、插入的三种情形与删除的四种情形，均为本文依据红黑树的公认定义自行整理与推导，不标教材页码。凡是本篇给出证明的地方，读者都可以按证明自行复核，不必依赖出处。

相关知识

二叉排序树（BST）（插入删除第一步都是 BST 操作）｜平衡二叉树（AVL）（左旋 / 右旋即其 RR / LL 旋转）｜B 树（与 4 阶 B 树等价）｜散列表（拉链法）｜查找算法的分析与应用

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习