《算法导论》第14章：数据结构的扩张 (Augmenting Data Structures)

本章提及了数据结构的“扩张”概念。当我们需要支持一种特殊操作的时候，应该优先考虑去扩展现有的数据结构，而不是自创一种。扩展的方法就是“加信息”，然后用原有的基本操作去维护它。作为例子，本章讲了“顺序统计树”和“区间树”，并给出了扩展数据结构的一般方法。

顺序统计树

需求

在 $O(\lg{n})$ 时间内算出任一元素的次序；在 $O(\lg{n})$ 时间内找出任一次序的元素。

扩展

在红黑树的结点中加入额外信息size，表示以自己为根的子树含有多少内部结点。显然我们有

$x.size=x.left.size+x.right.size+1$

新操作

要选出第 $i$ 小的元素，我们从根结点开始，查看左子树的大小。若大于 $i-1$，则返回左子树的第 $i$ 小元素；若等于 $i-1$，则自己就是要找的元素；若大于 $i-1$，则在右子树寻找第 $i-1-x.left.size$ 小的元素。

要算出任一元素 $p$ 的次序，则可以往上一直追溯到根，然后每路过一个作为右子的结点，把它兄弟子树的 $size$ 再加1的值累加起来，就能得到自己的次序。伪代码如下：

OS-RANK(T,x)
  r = x.left.size + 1
  y = x
  while y != T.root
    if y == y.p.right
      r = r + y.p.left + 1
    y = y.p
  return r

要证明该算法的正确性，可以用归纳法证明，每次进入while循环时，$r$ 都是 $x$ 在根为 $y$ 的子树中的次序。

维护

红黑树经过插入和删除之后，内部结构会发生变化，这时需要更新结点的 $size$。

插入时（修复前），只有一个叶子变成了内部结点，因此把根到新结点路径上的 $size$ 全部加 1 即可。做插入后的修复时，只有旋转操作会影响树的结构（可以去复习一下上一章的内容），其他都只是对颜色的改变。更重要的是，一次旋转只会影响两个结点的 $size$，这简直太棒了！按照下图的示意，我们只需要在旋转操作后加上两行代码即可（以左旋为例）：

y.size = x.size
x.size = x.left.size + x.right.size + 1

删除时（修复前），若 $z$ 是计生结点，则应更新z的父亲到根路径上的 $size$；否则它会有它的后继 $y$ 来顶替，此时应更新 $y$ 原本的父亲到根路径上的 $size$。无论如何，删除时的缺位结点都是用 $y$ 表示的（见上一章的代码），这样实现起来比较方便。做删除后的修复时，同样只有旋转操作改变了树的结构，因此处理方法与插入后的修复相同。

如何扩展数据结构

书中介绍了几个要点，它们之间不是顺序关系，而是平行关系：

1. 选择一个基本数据结构
2. 决定要加入什么额外信息
3. 确保该信息能在操作数据结构的过程中保持正确（例如插入、删除）
4. 实现新的操作

至于红黑树，书中提出了一个关于要点2的纲领，以保证信息维护的效率：

• 如果在每个结点上都维护一个新的属性 $f$，且对于任一结点 $x$，$x.f$ 都只由 $x$ 及其左右子决定，那么就可以保证每次插入或删除后都能在 $O(\lg{n})$ 的时间内修复 $f$ 的正确性。

区间树

需求

每个元素代表一个区间，用 $[low,high]$ 表示。现在给出一个区间 $i$，需要在 $O(\lg{n})$ 的时间内查询是否有能与之重合的元素 $i'$。区间 $i$ 与 $i'$ 重合的定义是：$i.low < i'.high$ 且 $i'.low < i.high$。

扩展

用红黑树的形式组织每个区间的 $low$，然后每个结点记录一个属性 $max$，表示以它为根的子树中所有结点的 $high$ 的最大值。$max$ 的定义符合上一节所说的“纲领”，因为 $x.max=\max(x.high,\ x.left.max,\ x.right.max)$。

新操作

INTERVAL-SEARCH(T,i)
  x = T.root
  while x != T.nil and i does not overlap x
    if x.left != T.nil and x.left.max >= i.low
      x = x.left
    else
      x = x.right
  return x

这份算法很巧妙，但不是那么直观，因为 $max$ 的含义不太清晰，所以也不好理解向左/向右找的判断条件，但我们可以抓住一个不变量，然后证明它的正确性：若树 $T$ 中存在与 $i$ 重合的元素，那么根为 $x$ 的子树里一定也有。

循环开始时，$x$ 为根，所以命题成立。

每次循环的过程中，

• 若 $x$ 没有左子或 $x.left.max < i.low$，应该往右走。若 $x$ 没有左子，显然只有往右走才可能找到；若 $x.left.max < i.low$，说明 $x$ 左子树中所有结点的 $high$ 都小于 $i.low$，从而不可能与 $i$ 重合，同样必须往右走。
• 若 $x$ 有左子且 $x.left.max >= i.low$，应该往左走。若左子树不含与 $i$ 重合的结点，那么取其中 $high$ 最大的结点 $i'$，有 $i.low<=x.left.max=i'.high$ 且 $i'.low>i.high$（否则就符合重合条件），又因为 $x$ 右子树中所有结点的 $low$ 都不小于 $i'.low$（红黑树性质），所以此时右子树也不可能有与 $i$ 重合的元素。也就是“若左边有，右边可能没有；若左边没有，根为x的整棵子树都没有”，所以必须往左走。

总地来说，每次循环前都保证了“若 $T$ 有，则 $x$ 树有”，且每次循环后能保证 $x$ 的某一子树也有，否则会推出“$x$ 树没有”的矛盾，从而维持了命题的正确性。建议多绕几遍加深理解。

循环结束后，根据跳出循环的条件有两个可能：若 $x$ 与 $i$ 重合，则已找到；若 $x$ 是 $T.nil$，则根据命题的逆否形式，可以推出树 $T$ 不存在与 $i$ 重合的元素。

维护

需要维护的只有 $max$，只要像前面顺序统计树那样维护 $size$ 一样就好了。