第17章 数据结构扩张 — 章节汇总

章节概览

本章介绍数据结构扩张（Augmenting Data Structures）——一种在现有数据结构上添加附加信息以支持新操作的系统化方法。核心思想是：在红黑树等平衡搜索树的每个节点上存储额外的属性，使得新操作可以在不改变渐近时间复杂度的前提下高效执行。本章通过三个小节逐步展开：先给出一个具体例子（顺序统计树），再抽象出一般方法论（四步法+红黑树扩张定理），最后展示第二个应用（区间树）。

---

17.1 动态顺序统计

小节	核心主题	关键结论
17.1 动态顺序统计	顺序统计树、OS-SELECT、OS-RANK	查询/排名均为 $O(\lg n)$

核心思路：在红黑树每个节点上新增 size 属性（子树中的内部节点数），支持在 $O(\lg n)$ 时间内查找第 $i$ 小的元素（OS-SELECT）和计算元素的秩（OS-RANK）。INSERT/DELETE 的额外代价仅为 $O(\lg n)$（沿路径更新 size），旋转的代价为 $O(1)$（仅更新2个节点）。

---

17.2 如何扩张数据结构

小节	核心主题	关键结论
17.2 如何扩张数据结构	四步法、红黑树扩张定理	系统化方法论

核心思路：将数据结构扩张抽象为四步法——（1）选择底层数据结构、（2）确定附加信息、（3）验证可维护性、（4）开发新操作。红黑树扩张定理是核心理论保证：只要附加信息可以在 $O(1)$ 时间内从节点及其子节点计算，就能在 $O(\lg n)$ 内维护。该定理为设计新数据结构提供了系统化的”检查清单”。

---

17.3 区间树

小节	核心主题	关键结论
17.3 区间树	区间重叠查询、INTERVAL-SEARCH	查询 $O(\lg n)$ 平均

核心思路：在红黑树基础上扩张，每个节点存储一个区间和一个 max 值（子树中所有区间的最大右端点）。INTERVAL-SEARCH 通过比较 x.left.max 与查询区间的左端点来决定搜索方向，平均 $O(\lg n)$。正确性由两个引理保证：向右走时左子树无重叠区间，向左走时右子树无重叠区间。

---

本章核心知识点

两种扩张数据结构对比

特性	顺序统计树	区间树
底层结构	红黑树	红黑树
附加属性	size（子树节点数）	max（子树最大右端点）
递推公式	$x.size=x.left.size+x.right.size+1$	$x.max=\max (x.int.high,x.left.max,x.right.max)$
核心操作	OS-SELECT、OS-RANK	INTERVAL-SEARCH
操作复杂度	$O(\lg n)$	$O(\lg n)$ 平均
维护代价	INSERT/DELETE 额外 $O(\lg n)$	INSERT/DELETE 额外 $O(\lg n)$
实际应用	数据库排名查询、排行榜	日历冲突检测、资源预约

红黑树扩张定理的核心条件

条件	满足的例子	不满足的例子
$f(x)$ 可在 $O(1)$ 时间内从 $x$、$x.left$、$x.right$ 计算	size、max、min、sum	子树高度、子树中第 $k$ 小元素

数据结构扩张四步法

步骤	内容	本章实例
1. 选择底层结构	红黑树	顺序统计树、区间树均用红黑树
2. 确定附加信息	size / max	顺序统计→size，区间树→max
3. 验证可维护性	$O(1)$ 局部可计算	size/max 均满足
4. 开发新操作	OS-SELECT/INTERVAL-SEARCH	利用附加信息设计新算法

---

与前序章节的知识关联

前序章节	关联方式
第13章 红黑树	红黑树是本章所有扩张的底层结构，INSERT/DELETE/ROTATE 操作是维护附加属性的基础
第12章 BST	二叉搜索树的 SEARCH/INSERT/DELETE 是红黑树操作的基础
第6章 堆排序	堆也支持顺序统计（HEAP-SELECT），但仅支持静态集合；顺序统计树支持动态集合
第16章 摊还分析	摊还分析可用于分析扩张数据结构的操作序列代价

---

学习路线

第17章学习路径：
  17.1 动态顺序统计（红黑树+size属性→OS-SELECT递归→OS-RANK向上回溯→INSERT/DELETE维护size→O(lg n)）
    → 17.2 如何扩张数据结构（四步法→红黑树扩张定理→O(1)局部可计算条件→定理证明→工程实例）
      → 17.3 区间树（区间重叠定义→max属性→INTERVAL-SEARCH→向右走/向左走正确性引理→应用场景）

学习建议

本章是Part V（高级数据结构）的入门章节，核心在于掌握”数据结构扩张”这一思维方式。17.1 是具体例子，重点理解 size 属性的递推定义和 OS-SELECT/OS-RANK 的递归/迭代逻辑。17.2 是方法论总结，重点掌握四步法和红黑树扩张定理的 $O(1)$ 局部可计算条件——这是判断一个扩张是否可行的关键准则。17.3 是第二个应用，重点理解 INTERVAL-SEARCH 的搜索方向决策逻辑和两个正确性引理。学完本章后，回顾第13章红黑树的旋转操作，理解为什么旋转只影响2个节点——这是扩张定理成立的关键。

---

参见Wiki

• 数据结构扩张 — 数据结构扩张的核心思想与一般流程
• 顺序统计树 — 红黑树扩张案例：动态顺序统计
• 区间树 — 红黑树扩张案例：区间重叠查询
• 数据结构扩张四步法 — 系统化扩张方法论
• 红黑树扩张定理 — 红黑树扩张的理论基础
• 区间重叠 — 区间重叠的判定条件

---

第17章-数据结构扩张 章节汇总