红黑树高度定理

概述

红黑树高度定理（Red-Black Tree Height Theorem）：一棵有 $n$ 个内部结点的红黑树的高度至多为 $2\lg (n+1)$。该定理是红黑树保证 $O(\lg n)$ 查找、插入、删除操作时间复杂度的核心基础。

定理陈述

形式化陈述

定理（CLRS Lemma 13.1 / Theorem 13.1）：设 $T$ 是一棵有 $n$ 个内部结点的红黑树，$h$ 为 $T$ 的高度，则 $h\le 2\lg (n+1)$

前提条件：

• $T$ 满足红黑树的五条性质（根为黑色、叶子 NIL 为黑色、红结点的子结点为黑色、每个结点到叶子的所有路径上黑色结点数相同）
• $n$ 为内部结点数（不含 NIL 哨兵结点）
• $h$ 为从根到最深叶子结点的路径长度（以边数计）

证明概要

证明思路

证明分为两步：先建立子树内部结点数与黑高度的指数下界关系，再利用红黑树性质将实际高度与黑高度联系起来。

引理 13.1：内部结点数下界

以结点 $x$ 为根的子树至少包含 $2^{\text{bh}(x)}-1$ 个内部结点，其中 $\text{bh}(x)$ 是 $x$ 的黑高度（从 $x$ 到其子树中任意叶子的路径上黑色结点数，不含 $x$ 本身）。

对 $\text{bh}(x)$ 用数学归纳法证明引理：

基例：$\text{bh}(x)=0$。此时 $x$ 的子结点均为 NIL 叶子，以 $x$ 为根的子树恰好包含 $x$ 自身，共 $1=2^0-1+1$ 个内部结点，即至少 $2^0-1=0$ 个内部结点。成立。

归纳假设：设对 $\text{bh}(x)=k$，以 $x$ 为根的子树至少包含 $2^k-1$ 个内部结点。

归纳步：设 $\text{bh}(x)=k+1$。$x$ 的每个子结点 $c$ 的黑高度至少为 $k$（因为 $x$ 本身是黑色，路径上经过 $x$ 后黑色结点数至少减少 1；若 $x$ 为红色，则 $c$ 的黑高度为 $k$；若 $x$ 为黑色，则 $c$ 的黑高度也为 $k$）。

由归纳假设，每个子树至少包含 $2^k-1$ 个内部结点。因此以 $x$ 为根的子树至少包含： $(2^k-1)+(2^k-1)+1=2^{k+1}-1$ 个内部结点（两个子树加上 $x$ 自身）。归纳完成。

定理证明：

设红黑树 $T$ 的根为 $r$，黑高度为 $\text{bh}(r)$。

由引理 13.1，$T$ 的内部结点数满足： $n\ge 2^{\text{bh}(r)}-1$

两边加 1 取对数： $\text{bh}(r)\le \lg (n+1)$

由红黑树性质 4（红结点的子结点为黑色），从根到叶子的任意路径上，红色结点数不超过黑色结点数（因为红色结点不能连续出现）。因此树的高度： $h\le 2\cdot \text{bh}(r)\le 2\lg (n+1)$

证毕。

关键推论

• 搜索时间复杂度：红黑树上的 SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR 操作均在 $O(h)=O(\lg n)$ 时间内完成
• 插入与删除时间复杂度：INSERT 和 DELETE 操作涉及 $O(\lg n)$ 次旋转和颜色调整，总时间 $O(\lg n)$
• 与 AVL 树的对比：AVL 树的高度上界为 $\approx 1.44\lg (n+2)$，比红黑树更严格，但红黑树在插入/删除时需要更少的旋转操作，实际性能更优
• 黑高度的范围：$\text{bh}(r)\ge \lfloor h/2\rfloor$，即黑高度至少是树高的一半

应用场景

• 算法导论 Ch13：红黑树高度定理是整个红黑树章节的理论基石，保证了所有动态集合操作的对数时间复杂度
• 标准库实现：C++ STL 的 std::map / std::set、Java 的 TreeMap / TreeSet 均基于红黑树实现，其性能保证直接依赖此定理
• 操作系统内核：Linux 进程调度器 CFS（Completely Fair Scheduler）使用红黑树管理进程的虚拟运行时间，$O(\lg n)$ 的操作复杂度保证了调度效率
• 数据库索引：部分内存数据库使用红黑树作为索引结构，对数高度保证了查询性能的可预测性

参见

• 二叉搜索树 — 红黑树的基础结构
• 安全边定理 — 另一类基于归纳法的定理证明范例
• B树高度定理 — B 树的高度上界，与红黑树形成对比