红黑树

概述

红黑树（Red-Black Tree, RBT） 是一种自平衡二叉搜索树，在每个节点上存储一个额外的颜色位（红色或黑色），通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，来确保没有一条路径会比其他路径长出两倍，从而保证树的高度为 $O(\lg n)$，使得基本动态集合操作在最坏情况下均为 $O(\lg n)$ 时间。

定义

红黑树

红黑树是一棵满足以下五条性质的二叉搜索树，其中每个节点额外包含一个存储位 color（RED 或 BLACK）：

1. 每个节点非红即黑。
2. 根节点是黑色的。
3. 每个叶节点（NIL）是黑色的。（所有叶子都是相同的 NIL 节点，也称为哨兵节点）
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。（即不能有两个连续的红色节点）
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

核心性质

高度上界

引理 13.1 的推论

一棵有 $n$ 个内部节点的红黑树的高度至多为 $2\lg (n+1)$。

证明思路：

设红黑树的高度为 $h$，根节点的黑高度为 $bh$。

• 由性质 4（红节点的子节点必为黑），可知从根到叶子的任何路径上，红色节点数不超过黑色节点数，因此 $h\le 2bh$。
• 由性质 5（黑高度一致性）和引理 13.1，以根为根的子树至少有 $2^{bh}-1$ 个内部节点，即 $n\ge 2^{bh}-1$，因此 $bh\le \lg (n+1)$。
• 综合可得：$h\le 2bh\le 2\lg (n+1)$。

因此，红黑树是一种近似平衡的二叉搜索树，最坏情况下树高不超过 $2\lg (n+1)$。

自平衡机制

红黑树通过旋转和变色两种基本操作来维护上述五条性质：

• 旋转：改变树的局部结构（见 旋转），$O(1)$ 时间
• 变色：改变节点的颜色，$O(1)$ 时间

插入操作最多需要 2 次旋转（见 RB-INSERT-FIXUP），删除操作最多需要 3 次旋转（见 RB-DELETE-FIXUP）。

与完美平衡树的关系

红黑树并不要求严格平衡（即左右子树高度差不超过 1），而是允许适度不平衡。一棵红黑树在最坏情况下，最长路径是最短路径的两倍长。这种”宽松”的平衡条件使得插入和删除操作比严格的平衡树（如 AVL 树）更高效，因为需要更少的旋转操作。

哨兵节点

红黑树使用一个统一的 NIL 哨兵节点（sentinel）来替代所有的 null 指针。这个哨兵节点是黑色的（满足性质 3），从而简化了边界条件的处理。使用哨兵后，所有叶子节点都指向同一个 NIL 节点，使得对叶子节点的操作不需要特殊处理。

历史背景

• 1972 年：Rudolf Bayer 发明了红黑树的前身——“对称二叉 B 树”（symmetric binary B-tree），这是一种 2-3-4 树的二叉树等价表示。
• 1978 年：Leonidas J. Guibas 和 Robert Sedgewick 在论文 “A Dichromatic Framework for Balanced Trees” 中正式将其命名为”红黑树”，并引入了红/黑颜色编码来简化 2-3-4 树的表示。

章节扩展

操作	时间复杂度	说明
查找 SEARCH	$O(\lg n)$	与普通 BST 相同，利用 BST 性质
插入 INSERT	$O(\lg n)$	插入 + 修复，最多 2 次旋转
删除 DELETE	$O(\lg n)$	删除 + 修复，最多 3 次旋转
最小值/最大值	$O(\lg n)$	沿左/右子树下降
前驱/后继	$O(\lg n)$	利用树的结构信息
旋转	$O(1)$	局部结构调整
扩张为顺序统计树	$O(\lg n)$	添加 size 属性，支持 OS-SELECT/OS-RANK
扩张为区间树	$O(\lg n)$	添加 max 属性，支持 INTERVAL-SEARCH

参见

• 黑高度 — 黑高度的定义与引理 13.1
• 旋转 — 左旋与右旋操作
• RB-INSERT-FIXUP — 插入修复的三种情况
• RB-DELETE-FIXUP — 删除修复的四种情况
• 额外黑色 — 删除修复中的”额外黑色”概念
• 二叉搜索树 — 红黑树的基础结构
• AVL树-vs-红黑树 — AVL 树与红黑树的对比
• 数据结构扩张 — 红黑树作为扩张的基础结构
• 红黑树扩张定理 — 保证旋转后附加信息可 $O(1)$ 维护的定理
• 顺序统计树 — 红黑树扩张案例：顺序统计
• 区间树 — 红黑树扩张案例：区间重叠查询