walkthrough · 5 property → 插入 / 查询 / 删除

red-black tree · 拆解与动手

为什么一棵 BST 会退化成链表、查找慢到 O(n)? red-black tree 用红/黑两种颜色 + 5 条 property，只靠局部的 recolor 与 rotation 就把树高稳定压在 O(log n)。从 property 直觉出发，先理解这 5 条规则其实是 2-3-4 tree 的翻译，再亲手单步插入看 fixup 怎么把破坏的平衡补回来，再走一遍查询的比较路径与最难的删除 double black 修复。每节都能改输入、点单步、随时看 5 条 property 的校验结果。阅读前需要了解 binary search tree (BST) 的基本规则：每个 node 左子树的值更小、右子树更大，查找/插入沿比较路径下降。另一种用随机化达成平衡的 BST 见 treap 系列。

本页依次：5 条 property 与 black height → 规则从哪来：2-3-4 tree → rotation → 单步插入 → 查询与删除 → 延伸：AVL 之争与来历。

颜色约定：本系列里红 node 画成红色实心圆，黑 node 画成深灰/黑实心圆，NIL leaf 是淡灰小方块（始终黑）。当前操作涉及的 node 用橙色描边高亮。

1 · 为什么需要 self-balancing:5 条 property 与 black height

BST 的查找/插入/删除都是 O（树高）。树高最好是 O(log n)，可一旦输入有序地到来，naive BST 会一路只往一边长——退化成一根链表，树高 O(n)，查找退回线性扫描。self-balancing BST 的使命就是：无论插入顺序如何，都把树高压在 O(log n)。

1.1 · red-black tree 的 5 条 property

每个 node 要么红、要么黑。
根 node 是黑色。
每个 NIL leaf 视为黑色。
红 node 的两个孩子都是黑色（等价于：不存在两个相连的红 node）。
从任一 node 到它所有后代 NIL 的每条路径，经过的黑 node 数目相同。

把「从某 node 到后代 NIL 路径上的黑 node 数」叫做该 node 的 black height。「黑高一致」这条 property 说每个 node 的 black height 是良定义的（各路径一致）。

1.2 · 为什么这 5 条 ⇒ O(log n)

关键直觉：由 property「无连续红 node」，红 node 不能相连，所以任意一条根到 NIL 的路径上，红 node 数 ≤ 黑 node 数，于是最长的路径 ≤ 最短路径长度的 2 倍。再加上 property「各路径 black height 相等」保证所有路径黑 node 数相同，整棵树的「宽度分布」就被约束得相当均匀，推得树高 ≤ 2·log₂(n+1)——稳定的 O(log n)。

1.3 · 动手看：red-black tree vs naive BST

下面两棵树接受同一串值。左边是 red-black tree（每插一个就自动 self-balancing），右边是 naive BST（不做任何平衡）。使用「有序序列」按钮：naive BST 立刻退化成斜链，而 red-black tree 的高度几乎不变。

读数提示:node 数 n 相同的情况下，red-black tree 高度接近 log₂n,naive BST 在有序输入下高度等于 n−1。black height 是 red-black tree 独有的统计量——它一定 ≤ 实际高度，正是它的「一致」撑起了平衡。

这 5 条规则的来历不是凭空规定——它们是 2-3-4 tree 的二叉翻译，见「红黑树其实是 2-3-4 tree」一节。

2 · 规则从哪来：红黑树其实是 2-3-4 树

5 条 property 讲了它们推出 O(log n)——那是规则的后果。可这 5 条规则本身为什么长这样、凭什么这么定？答案是：红黑树不是从 AVL tree 改来的，它是另一种完美平衡树——2-3-4 tree——的一种二叉表示。把 2-3-4 tree 看懂，5 条 property 就成了它的「逐句翻译」，无需死记。

2.1 · 先认识 2-3-4 tree

普通 BST 每个 node 只装 1 个 key。2-3-4 tree 放宽了：一个 node 能装 1~3 个 key,key 多了分支也多——装 1 个 key 的叫 2-node（2 个孩子）、装 2 个的叫 3-node（3 个孩子）、装 3 个的叫 4-node（4 个孩子）。它的关键性质：所有叶子永远在同一层——无论插入顺序如何，这棵树都保持完美平衡，不会一边高一边低。

2.2 · 翻译表：每种 node 对应一小簇红黑 node

Guibas & Sedgewick (1978) 的做法：用普通二叉树「画出」2-3-4 tree——一个 2-3-4 node 里的第一个 key 当黑色 anchor，多出来的 key 拆成红色子 node 挂在它身边。红色就是「我和上面那个黑 node 本是同一个 2-3-4 node」的标记。下面三张图里，2-3-4 node 的每个格子已经按它在红黑树里的颜色着色，右侧黄色光晕圈住的「同一簇」就是它还原成的那个 2-3-4 node:

一个 3-node 有两种合法画法（红挂左边或右边）。本节统一用「左倾」：{a,b} → 黑 b、左红 a。所以本节映射出的红黑树形状不一定等于 单步插入那条 CLRS 自底向上插入得到的树——它只是「同一组 key 的一种合法红黑树」。重点看的是对应关系，不是某棵具体的树。

2.3 · 动手：同一串值，左右两棵树

下面左右两棵树接受同一串值。左边是 2-3-4 tree（每个 node 1~3 个 key），右边是它实时翻译出的红黑树。一个一个插，你会看到：左边 4-node 一旦再撑大就裂开、把中键上推（这正对应右边的 recolor/rotation），而所有叶子始终齐平。

2.4 · 于是 5 条 property 全是「翻译」出来的

property「各路径 black height 相等」 ⇐ 2-3-4 tree 所有叶子在同一层。每个 2-3-4 node 恰好贡献 1 个黑 anchor，所以红黑树每条根→NIL 路径上的黑 node 数 = 2-3-4 tree 的层数（上面 verdict 里这两个数相等）。

property「无连续红 node」 ⇐ 一个 2-3-4 node 最多装 3 个 key，翻译成红黑树就是一个黑 anchor 最多带 2 个红孩子——不可能出现「红孩子的红孩子」（那得是装了 4+ 个 key 的 node,2-3-4 tree 里不存在）。

property「根为黑」、property「节点非红即黑」、property「NIL为黑」:「节点非红即黑」来自「红/黑只是 anchor/同簇两种身份」；「根为黑」「NIL为黑」是为简化代码定的工程约定。

所以红黑树的规则可以从 2-3-4 tree 直接推导：理解了 2-3-4 tree，那 5 条 property 自然成立。这棵树的祖先是 Rudolf Bayer 1972 年的 symmetric binary B-tree，后来 Guibas & Sedgewick 给它「上色」，成了今天广泛使用的 red-black tree（历史细节见「AVL 之争、到处是它、与它的来历」一节）。

3 · rotation：旋转动了哪几根指针，为什么旋完还是合法 BST

insert 与 delete 的 fixup 里到处在调 rotation，但旋转本身只是一个纯结构操作，和颜色完全无关。它做的事就一句话：让一对父子节点上下对调，同时把夹在中间的那棵子树重新挂一下——一共只改 3 根指针。这一节先理解这个原子操作，插入与删除两节的 fixup 才不会是黑盒。

3.1 · 左旋 / 右旋：互为镜像，也互为逆操作

       x                              y
      / \         左旋 x  ▸           / \
     a   y      ◂  右旋 y           x   c
        / \                        / \
       b   c                      a   b

左旋 x：把 x 的右孩子 y 提上来，x 沉成 y 的左孩子。右旋 y 是它的逆，转回去。注意中间那棵子树 b：它本来挂在 y 的左边，旋转后改挂到 x 的右边——这是唯一改挂父节点的子树。

为什么可以任意旋转？因为旋转严格保持中序遍历 (inorder) 不变。上图无论左旋右旋，中序都是 a x b y c——而「中序升序」正是 BST 的定义。所以旋转不会破坏 BST 性质，只改变树的形状（谁高谁矮），因此平衡树可以安全地用它降低过深的分支。

3.2 · 动手：对 root 左旋 / 右旋，观察 inorder 不变

下面是上图那棵子树（取 a=10, x=20, b=30, y=40, c=50，颜色这里只是装饰，旋转与颜色无关）。反复点「左旋 root」「右旋 root」来回切换，看 root 升降、中间子树 30 改挂，而最下方的 inorder 始终是 10 20 30 40 50。

3.3 · 那么：什么时候才需要旋转？

旋转是调整结构的工具，只在 recolor 修不动时才用。插入里只有叔叔黑的两种情形要旋（情形2 先把内侧转成外侧、情形3 绕祖父旋一次）；删除里情形1/3/4 用旋转换出黑兄弟、消除双黑。具体「在哪一步、旋哪边」由 fixup 决定——去单步插入和删除两节看旋转被嵌进完整流程里逐步播放。

真实代码比这里多一点：上面为聚焦只接了「父子 + 中间子树」3 根指针（对 root 旋转）。在完整实现里（见 rbt.ts 的 leftRotate）还要多接 parent 指针：让 y 认领 x 原来的父亲、并替 x 在祖父那边的左/右槽位站好。多出来的几行全是「把 y 缝回原位」，旋转的核心仍是这 3 步。

4 · 插入：下降染红，再 fixup

插入分两段。第一段是普通 BST 插入，第二段是 red-black tree 独有的修复 (fixup)。fixup 会反复用到 rotation，若不熟悉其指针操作可先看 rotation 节:

按 BST 规则从根下降，找到空位插入新 node，把它染红。（染红是为了不破坏 property「各路径 black height 相等」的 black height。）如果父 node 也是红 → 违反了 property「无连续红 node」，需要 fixup，看 uncle node 的颜色分情形：

情形1 uncle 红：父与 uncle 都 recolor 为黑、祖父 recolor 为红，问题上移到祖父继续。
情形2 uncle 黑且当前是「内侧」孩子：先 rotation 把它扳成外侧，转成情形3。
情形3 uncle 黑且当前是「外侧」孩子：父 recolor 为黑、祖父 recolor 为红，绕祖父 rotation 一次，平衡恢复。

最后无条件把根染黑（property「根为黑」）。

下面输入一个数、点「插入」，然后用「下一步」逐步看下降、染红、每次 recolor/rotation；旁白会说清属于哪种情形。每次插入完成后展示 5 条 property 的校验结果。

为什么新 node 总染红？插红 node 不改变任何路径的 black height，只可能违反 property「无连续红 node」（红-红相连），而 property「无连续红 node」是「局部」可修的；若插黑 node，几乎必然破坏 property「各路径 black height 相等」的全局 black height 一致，要修反而更难。

5 · 查询与删除：比较路径与 double black 修复

先看查询——它和普通 BST 完全一样，不关心颜色：从根开始，目标比当前小就向左、大就向右，逐次比较直到命中或到达 NIL leaf。下面单步走一遍，高亮树上的比较路径。删除修复会用到 rotation 节的旋转操作与插入节的分情形思路，建议先读这两节。

5.1 · 查询：逐次比较的下降路径

5.2 · 删除：BST 删除 + double black 修复

删除先做标准 BST 删除：被删 node 若有两个孩子，就用它的 in-order successor（右子树最小者）顶上去并继承其颜色。真正麻烦的是：如果被移走的那个 node 是黑色，它所在路径就凭空少了一个黑 node——black height 被破坏，我们说顶替它的位置背上了一重额外的黑，称作 double black。修复就是把这重多余的黑想办法消掉：

设 x 背着 double black、w 是 x 的 sibling:

情形1 sibling w 红：w recolor 为黑、父 recolor 为红，绕父 rotation，换出一个黑 sibling，转入下面情形。
情形2 w 黑且 w 的两个孩子都黑：把 w recolor 为红，等于把多余的黑「上交」给父 node，问题上移。
情形3 w 黑、远侄黑、近侄红：rotation + recolor，把它转成情形4。
情形4 w 黑且远侄红：一次 rotation + recolor,double black 被彻底消除，结束。

下面这棵树由确定性序列建成。输入一个存在的值删除它，用「下一步」逐步看 BST 删除与 double black 修复；每步后都展示 5 条 property 的校验——你会看到中途可能短暂出现 double black，但收尾时 property 总能全部恢复。

结论：不管中途经历几次 rotation 和 recolor，只要删除算法正确，收尾时 5 条 property 必然全部回到「✓」。本节用的 checkInvariants 与 remove 出自同一个共享模块 rbt.ts，经过 5000 次混合增删的随机化（确定性）压测，全程 property 不破。

6 · 延伸：AVL 之争、应用、来历

这是一节纯读的选读内容——没有交互，只讲三件事：红黑树和 AVL tree 如何取舍、为什么它在工业界无处不在、以及它是怎么来的。结论先行：红黑树的优势不在「样样第一」，而在「样样够用」。

6.1 · 红黑树 vs AVL tree：两种平衡哲学

很多人以为红黑树是 AVL tree 的升级版，其实不是——它们是针对不同目标的两种独立设计。AVL tree(Adelson-Velsky & Landis,1962)规则很严：任一 node 的左右子树高度差 ≤ 1，于是树尽量矮、查询路径短。红黑树只要求黑高一致、红 node 不相连，平衡条件松得多——代价是树可能更高一些。

「红黑树高是 AVL 的 2 倍」是个常见误解。那只是上界:AVL tree 高度 ≈ ${1.44\cdot \log _2n}$ ，红黑树 ≤ ${2\cdot \log _2(n+1)}$ 。两者都是 O(log n)，实际差距远没到 2 倍。查 100 万个数，AVL 约 20 层、红黑树最坏也就 ~30 层出头——现代机器上这点路径差几乎感觉不到。

真正的分野在维护代价。平衡条件越严，改动后要做的修复操作越多：

维度	AVL tree	red-black tree
平衡条件	左右子树高差 ≤ 1	黑高一致 · 红不相连
树高（n 个 node）	≤ ~1.44 log₂n	≤ 2 log₂n
插入时旋转	≤ 2 次	≤ 2 次
删除时旋转	最坏 O(log n) 次	≤ 3 次
更擅长	查询（树更矮）	增 / 删（修复更少）
诞生	1962	1972 / 1978

关键就在删除那行：AVL tree 删完可能要沿着回根的路一路检查、一路旋转(最坏 O(log n) 次)；红黑树因为约束松，删除至多 3 次旋转即可完成（见删除节的 4 种情形）。所以这是一种权衡：红黑树用「查询略慢一点」换来「增删时修复操作少很多」。哪个更合适取决于负载——读多写少偏 AVL，频繁增删偏红黑树。大多数通用容器是后者。

关于那些「实测毫秒数」：网上流传过一组对比（如随机插入百万条 AVL ~920ms、红黑树 ~680ms，顺序插入差距更大），但没有严格出处、未注明机器/实现/编译选项，只能当作趋势示意：增删密集时红黑树通常更快、纯查询时 AVL 略胜。不应把具体数字当结论。

6.2 · 为什么到处都是红黑树

常用的语言运行时与系统内核里它随处可见：

Java:TreeMap / TreeSet 就是红黑树；HashMap 自 Java 8 起，单个桶内冲突过多（默认 > 8 个）会把链表转成红黑树，把最坏查找从 O(n) 拉回 O(log n)。
C++ STL:std::map / std::set / multimap / multiset 几乎都用红黑树实现（标准只要求有序 + 对数复杂度，各家实现不约而同选了它）。
Linux 内核：调度器的运行队列、各种定时器、区间管理等多处都用红黑树（也有子系统后来换了别的结构，如虚拟内存区 VMA 在较新内核改用了 maple tree）。
函数式语言:persistent（不可变）红黑树很常见（如 Okasaki 的经典实现）——每次插入只重平衡路径附近常数个 node，复制开销小。

大家都选它，原因就三条：增、删、查三者最均衡，没有明显短板；省内存——颜色只要 1 个 bit，很多实现直接塞进指针的低位，几乎不额外占地方；取最小 / 最大极快——一路向左（或向右）走到底即可，这对「下一个该执行哪个任务」之类的调度场景特别合用。

6.3 · 来历：一棵被「上了色」的 B-tree

红黑树的前身是 Rudolf Bayer 1972 年提出的 symmetric binary B-tree。Bayer 更早还（与 McCreight 一起）发明了 B-tree——那才是数据库领域的主角，这棵二叉变体当时并未受到同等重视。1978 年，Guibas & Sedgewick 在论文《A Dichromatic Framework for Balanced Trees》里给它「上色」、起了「红黑」这个名字、理清了那套框架，这才有了今天广泛使用的 red-black tree。

它和「红黑树其实是 2-3-4 tree」一节讲的结构是同一回事的两种表示：红黑树正是 2-3-4 tree（一种阶为 4 的 B-tree）的二叉表示——所以说它是「被上色的 B-tree」并不夸张。

它真正的启示不是那 5 条规则，也不是几十行旋转代码，而是：在真实工程里，一个数据结构不需要在每个维度都最好，只要每个维度都「够用」、又被主流实现采纳，就可能成为经典。