黑高度

概述

黑高度（black-height, bh） 是红黑树中衡量从某节点到叶子路径上黑色节点数量的关键指标。它是红黑树第五条性质（黑高度一致性）的数学表达，也是推导红黑树高度上界的核心工具。

定义

黑高度

设节点 $x$ 为红黑树中的一个节点（$x$ 可以为 NIL 哨兵节点）。从节点 $x$ 出发（不包含 $x$ 本身），到达任意一个后代叶节点（NIL）的简单路径上，黑色节点的个数称为节点 $x$ 的黑高度，记作 $bh(x)$。

定义要点

• 不包含节点 $x$ 本身：$bh(x)$ 只计算从 $x$ 的子节点开始到 NIL 的黑色节点数。
• NIL 节点的黑高度为 0：$bh(\text{NIL})=0$，因为 NIL 没有子节点，路径上没有黑色节点。
• 红黑性质 5 的等价表述：对红黑树中的任意节点 $x$，从 $x$ 到其所有后代 NIL 的路径上的黑色节点数相同，即 $bh(x)$ 是良定义的（不依赖于路径的选择）。

示例

        B (bh=2)
       / \
      R   B (bh=1)
     /   / \
    B   R   B (bh=0)
   /   /   /
  NIL NIL NIL

• 根节点（黑色）的 $bh=2$：到 NIL 的路径上各有 2 个黑色节点（不计根节点本身）。
• 左子节点（红色）的 $bh=1$：到 NIL 的路径上有 1 个黑色节点。
• 所有叶子 NIL 的 $bh=0$。

核心性质

引理 13.1

引理 13.1

以某一节点 $x$ 为根的子树中，内部节点个数至少为 $2^{bh(x)}-1$。

证明（对 $bh(x)$ 进行数学归纳法）：

基础情况：当 $bh(x)=0$ 时，节点 $x$ 必为 NIL（哨兵节点），以 $x$ 为根的子树中没有内部节点，内部节点个数为 $0=2^0-1$。基础情况成立。

归纳假设：假设对于 $bh(x)=k$，以 $x$ 为根的子树至少有 $2^k-1$ 个内部节点。

归纳步骤：考虑 $bh(x)=k+1$ 的节点 $x$。设 $x$ 的左右子节点分别为 $x.left$ 和 $x.right$。

• 若 $x$ 为红色，则由红黑性质 4，$x.left$ 和 $x.right$ 均为黑色，因此： $bh(x.left)=bh(x.right)=bh(x)-1=k$
• 若 $x$ 为黑色，则 $x.left$ 和 $x.right$ 的黑高度为： $bh(x.left)=bh(x.right)=bh(x)-1=k$

无论 $x$ 是红是黑，$bh(x.left)=bh(x.right)=k$。

由归纳假设：

• 以 $x.left$ 为根的子树至少有 $2^k-1$ 个内部节点
• 以 $x.right$ 为根的子树至少有 $2^k-1$ 个内部节点

因此，以 $x$ 为根的子树的内部节点总数至少为： $(2^k-1)+(2^k-1)+1=2^{k+1}-1$

其中最后的 $+1$ 是节点 $x$ 本身。归纳步骤成立。

由数学归纳法，引理得证。$■$

推论：红黑树的高度上界

由引理 13.1 可直接推导红黑树的高度上界：

1. 设红黑树有 $n$ 个内部节点，根节点为 $r$，黑高度为 $bh(r)$。
2. 由引理 13.1：$n\ge 2^{bh(r)}-1$，因此 $bh(r)\le \lg (n+1)$。
3. 由红黑性质 4（红节点的子节点必为黑），从根到叶子的路径上，红色节点数不超过黑色节点数，因此树高 $h\le 2\cdot bh(r)$。
4. 综合可得：$h\le 2\lg (n+1)$。

章节扩展

黑高度是红黑树几乎所有分析的基础：

• 插入分析：新节点着红色不改变任何路径的黑高度，因此插入最多破坏性质 2 或性质 4。
• 删除分析：删除黑色节点会减少某条路径的黑高度，需要通过 额外黑色 机制来修复。
• 旋转分析：旋转操作不改变任何节点的黑高度，只改变局部结构。

参见

• 红黑树 — 红黑树的完整定义与五条性质
• 旋转 — 旋转操作
• RB-INSERT-FIXUP — 插入修复
• RB-DELETE-FIXUP — 删除修复