红黑树扩张定理

概述

红黑树扩张定理（Red-Black Tree Augmentation Theorem）是 数据结构扩张 的核心理论基础。该定理保证：在红黑树的每个节点上添加额外属性后，只要这些属性可以在不涉及旋转的操作中 $O(1)$ 维护，那么在旋转操作中也能在 $O(1)$ 时间内维护。这一定理极大地简化了红黑树扩张的正确性论证，是构建 顺序统计树 和 区间树 等扩张结构的理论基石。

定义

红黑树扩张定理（定理陈述）

设 $T$ 是一棵有 $n$ 个内部节点的红黑树。对 $T$ 的每个节点 $x$ 添加一个附加域 $f(x)$，且 $f(x)$ 的值可以从 $x$ 的信息及其左右子节点的信息中在 $O(1)$ 时间内计算得出，即： $f(x)=g(x.\text{info},f(x.\text{left}),f(x.\text{right}))$ 其中 $g$ 是某个可以在 $O(1)$ 时间内计算的函数。

则对 $T$ 执行一次旋转操作（LEFT-ROTATE 或 RIGHT-ROTATE）后，所有受影响节点的 $f$ 值可以在 $O(1)$ 时间内重新计算并恢复正确。

定理的形式化表述

更严格地，设旋转操作涉及的节点为 $x$ 和 $y$（$y$ 是 $x$ 的一个子节点），则：

1. 旋转后，树中只有 $O(1)$ 个节点的 $f$ 值可能发生变化
2. 这些节点的 $f$ 值都可以在 $O(1)$ 时间内重新计算
3. 因此，旋转操作维护附加信息的总开销为 $O(1)$

证明思路

关键观察

红黑树的旋转操作（LEFT-ROTATE 和 RIGHT-ROTATE）是一种局部操作，它只改变树中两个节点 $x$ 和 $y$ 之间的父子关系，以及它们各自的一个子节点的归属。

以左旋为例（$y$ 是 $x$ 的右孩子）：

旋转前：          旋转后：
    x                y
   / \              / \
  a   y      →     x   c
     / \          / \
    b   c        a   b

证明步骤

第一步：确定受影响的节点

旋转操作只改变了以 $x$ 和 $y$ 为根的两棵子树的结构。因此，$f$ 值可能发生变化的节点只有 $x$ 和 $y$（以及它们的祖先节点）。

第二步：祖先节点的 $f$ 值不受影响

对于 $x$ 和 $y$ 的任何共同祖先 $z$，旋转前后以 $z$ 为根的子树所包含的节点集合完全不变（只是内部结构发生了变化）。因此，如果 $f(z)$ 仅依赖于 $z$ 的子树中的信息（而非子树的具体结构），则 $f(z)$ 的值不变。

注意

这里需要 $f$ 满足一个条件：$f$ 的值只依赖于子树的内容（包含哪些节点），而不依赖于子树的形状（节点的具体排列方式）。对于 size、max、sum 等聚合信息，这一条件自然满足。

第三步：$x$ 和 $y$ 的 $f$ 值可在 $O(1)$ 内重新计算

由于 $f(x)=g(x.\text{info},f(x.\text{left}),f(x.\text{right}))$，且 $g$ 为 $O(1)$ 计算，旋转后 $x$ 的左右子节点发生了变化，但 $f(x)$ 的新值可以直接从新的子节点的 $f$ 值中 $O(1)$ 计算得出。同理，$f(y)$ 也可以 $O(1)$ 计算。

第四步：更新顺序

需要注意的是，必须先更新”更深层”的节点，再更新”更浅层”的节点。在左旋中：

• 先更新 $x$（因为 $x$ 现在是 $y$ 的子节点）
• 再更新 $y$（因为 $y$ 现在是 $x$ 的父节点）

这保证了在计算 $f(y)$ 时，$f(x)$ 已经是正确的值。

结论：旋转操作后，最多需要更新 2 个节点的 $f$ 值，每个更新为 $O(1)$，因此总开销为 $O(1)$。$■$

生活化类比

想象一个公司组织架构（树结构），每个部门经理汇报自己部门的总人数（这就是附加信息 $f$）。

一次”旋转”就像是两个部门之间交换了一些下属团队。比如，技术部（$x$）下面的产品组（$y$）独立出来，产品组升级为与技术部平级，同时技术部的一些团队划归产品组管辖。

在这个调整中：

• 只有技术部和产品组两个部门的总人数需要重新计算
• 技术部的新人数 = 剩余团队的人数之和
• 产品组的新人数 = 原有团队人数 + 从技术部划过来的团队人数
• 更高层（CEO等）看到的总人数完全不变（因为总员工数没变）

这就是红黑树扩张定理的直观含义：局部结构调整只影响局部的统计信息。

核心性质

性质1：旋转维护开销有上界

无论红黑树有 $n$ 个节点还是 $n^2$ 个节点，旋转操作维护附加信息的开销始终为 $O(1)$，与树的大小无关。这是因为旋转是局部操作，影响的节点数恒定。

性质2：附加信息的”可聚合性”是关键

定理成立的核心前提是 $f$ 的可聚合性：$f(x)$ 可以从 $f(x.\text{left})$ 和 $f(x.\text{right})$ 中 $O(1)$ 计算。如果 $f$ 需要遍历整棵子树才能计算（例如”子树的中序遍历序列”），则定理不适用。

性质3：插入和删除的维护开销为 O(lg n)

虽然单次旋转的维护开销为 $O(1)$，但红黑树的插入操作最多触发 $O(\lg n)$ 次旋转（实际最多 2 次），删除操作最多触发 $O(\lg n)$ 次旋转（实际最多 3 次）。此外，插入和删除还需要沿路径更新所有祖先节点的 $f$ 值，路径长度为 $O(\lg n)$。因此，插入和删除的总维护开销为 $O(\lg n)$，与基础操作本身的复杂度相同。

性质4：广泛适用性

该定理适用于任何满足可聚合性条件的附加信息，包括但不限于：

附加信息 $f$	聚合函数 $g$	应用
$\text{size}$	$\text{left.size}+\text{right.size}+1$	顺序统计树
$\text{max}$	$\max (\text{key},\text{left.max},\text{right.max})$	区间树
$\text{min}$	$\min (\text{key},\text{left.min},\text{right.min})$	范围最小值查询
$\text{sum}$	$\text{key}+\text{left.sum}+\text{right.sum}$	子树求和
$\text{height}$	$1+\max (\text{left.height},\text{right.height})$	平衡检测

定理的应用意义

红黑树扩张定理的价值在于它将”验证附加信息可维护性”这一步从逐操作分析简化为验证可聚合性。在 数据结构扩张四步法 的第三步中，我们不再需要逐一分析每种旋转场景，只需验证 $f$ 是否满足可聚合性条件，即可由定理保证旋转后 $f$ 可在 $O(1)$ 内维护。

这大大降低了数据结构扩张的难度和出错概率，使得红黑树成为数据结构扩张的首选基础结构。

参见

• 红黑树 — 定理所适用的基础数据结构
• 数据结构扩张 — 定理所支撑的核心技术
• 数据结构扩张四步法 — 定理在第三步验证中的应用
• 顺序统计树 — 定理的经典应用：size 属性的维护
• 区间树 — 定理的经典应用：max 属性的维护