红黑树扩张定理

概述

红黑树扩张定理（Red-Black Tree Augmentation Theorem）：对红黑树 $T$ 进行扩张（在每个结点上增加额外的信息字段），只要扩张信息可以在 $O(1)$ 时间内由子结点的信息计算得到，则所有动态集合操作（插入、删除、旋转）仍可在 $O(\lg n)$ 时间内完成，且扩张属性在修改后得到正确维护。

定理陈述

形式化陈述

定理（CLRS Theorem 14.1）：设 $T$ 是一棵红黑树，对其每个结点 $x$ 增加一个额外字段 $a(x)$，满足以下条件：

1. $a(x)$ 的值仅依赖于 $x$ 的信息及其左子结点 $\text{left}(x)$ 和右子结点 $\text{right}(x)$ 的 $a$ 值，即 $a(x)$ 可以在 $O(1)$ 时间内由 $a(\text{left}(x))$ 和 $a(\text{right}(x))$ 计算得出
2. $a(x)$ 可以在 $O(1)$ 时间内由 $a(x)$ 的前驱或后继的 $a$ 值更新

则对 $T$ 执行插入或删除操作后，可以在 $O(\lg n)$ 时间内更新所有受影响结点的 $a$ 值，使得扩张属性在整个树中保持正确。

形式化条件： $a(x)=f(x.\text{key},x.\text{data},a(\text{left}(x)),a(\text{right}(x)))$ 其中 $f$ 是一个 $O(1)$ 时间可计算的函数。

证明概要

证明思路

证明的关键在于分析红黑树修改操作（插入、删除）对树结构的影响范围，以及旋转操作对扩张信息的影响。

步骤 1：分析旋转操作对扩张信息的影响

红黑树的插入和删除修复过程中，唯一改变树结构的操作是旋转（LEFT-ROTATE 和 RIGHT-ROTATE）。

以 LEFT-ROTATE(T, x) 为例（将结点 $x$ 的右子结点 $y$ 旋转上来）：

• 旋转仅影响 $x$ 和 $y$ 两个结点的子树关系
• 旋转后，需要重新计算 $a(x)$ 和 $a(y)$ 的值
• 此外，$x$ 和 $y$ 的祖先结点中，只有 $y$ 的原父结点 $p$ 的 $a$ 值可能需要更新（因为 $p$ 的某个子结点从 $x$ 变成了 $y$）
• 更新路径：从 $y$ 向上到根，每层只需 $O(1)$ 时间

旋转后更新 $a$ 值的总时间：$O(\lg n)$（最多更新从旋转点到根的路径上的所有结点）

步骤 2：分析插入操作

插入操作分为两步：

1. 标准 BST 插入：将新结点作为叶子插入，然后沿插入路径向上回溯，更新祖先的 $a$ 值。路径长度为 $O(\lg n)$，每层 $O(1)$ 时间，总计 $O(\lg n)$
2. 插入修复（INSERT-FIXUP）：最多执行 $O(\lg n)$ 次旋转，每次旋转后需要 $O(\lg n)$ 时间更新 $a$ 值。但由于旋转是沿路径向上进行的，所有旋转的更新可以合并为一次从最终位置到根的遍历，总时间仍为 $O(\lg n)$

步骤 3：分析删除操作

删除操作同样分为两步：

1. 标准 BST 删除：删除结点后，从删除位置向上到根更新 $a$ 值，时间 $O(\lg n)$
2. 删除修复（DELETE-FIXUP）：最多执行 $O(\lg n)$ 次旋转，与插入类似，所有旋转的 $a$ 值更新可合并为一次向上遍历，总时间 $O(\lg n)$

步骤 4：综合结论

• 旋转不改变红黑树性质（这是红黑树的基本定理），因此旋转后树仍为合法红黑树
• 扩张信息的更新时间与旋转次数线性相关，而旋转次数为 $O(\lg n)$
• 因此，扩张后的红黑树的所有动态集合操作仍在 $O(\lg n)$ 时间内完成

证毕。

关键推论

• 顺序统计树：在红黑树结点中增加子树大小字段 $\text{size}(x)$，可在 $O(\lg n)$ 时间内支持 OS-SELECT（第 $i$ 小元素）和 OS-RANK（元素排名）操作。$\text{size}(x)=\text{size}(\text{left}(x))+\text{size}(\text{right}(x))+1$ 满足 $O(1)$ 计算条件
• 区间树：在红黑树结点中增加 $\text{max-end}$ 字段（以 $x$ 为根的子树中所有区间的最大右端点），可在 $O(\lg n)$ 时间内支持区间查找操作
• 通用扩张框架：该定理提供了一个通用的数据结构扩张方法论——只要附加信息满足”局部可计算”条件，就可以在不增加渐近时间复杂度的前提下增强数据结构的功能

应用场景

• 算法导论 Ch14：顺序统计树（OS-TREE）是该定理的直接应用，支持动态集合上的顺序统计查询
• 算法导论 Ch14：区间树（INTERVAL-TREE）利用扩张信息高效查找与给定区间重叠的所有区间
• 文本编辑器：文本编辑器的行号计算可以使用顺序统计树，在 $O(\lg n)$ 时间内定位任意行
• 计算几何：区间树广泛应用于计算几何中的区间查询问题，如矩形交集检测

参见

• 二叉搜索树 — 红黑树扩张的基础结构
• 红黑树高度定理 — 红黑树 $O(\lg n)$ 高度上界是扩张定理成立的前提
• B树高度定理 — B 树同样支持数据结构扩张，适用于磁盘场景