算法导论（十四）－－数据结构的扩张

有些时候，我们需要在一些标准的数据结构（比如双链表、散列表或二叉查找树）上增加一些信息，以便编入新的操作。下面给出一个红黑树进行扩充的例子。

动态顺序统计

在红黑树的每个结点，除了基本的color, left, right , parent域，还增加一个size域，来记录以该结点为根的子树的结点数。一个结点的size可以由它的两个子结点得到：
x.size = x.left.size + x.right.size + 1　（T.nil.size为0。）
基于这个新加的域，我们便可增加新的操作，比如选择第i小的元素：

OS_SELECT(x, i) {
1   r = x.left.size + 1;
2      if i == r
3            return x;
4   else if i < r
5           return OS_SELECT(x.left, i);
6   else
7            return OS_SELECT(x.right, i-r);
}

它其实与第9章里的基本快速排序思想的选择算法差不多。
我们还可以在该数据结构里找到某个元素的秩（即元素在集合的排序）：

OS_RANK(T, x) {
1      r = x.left.size + 1;
2   y = x;
3      while y != T.root {
4            if y == y.parent.right
5                  r = y.parent.left.size + 1;
6            y = y.parent;
7      }
8      return r;
}

接下来讨论如何维护该数据结构中的size域。
在插入元素时，分两阶段，阶段一：从根开始向下遍历， 直到元素找到可以插入的位置；阶段二：通过旋转来维护红黑性质。在阶段一，我们只需在遍历时经由的所有结点的size增加1便可，时间为 O(lg(n))，在阶段二最多会有O(lg(n))次旋转，每次旋转只需O(1)的时间：重新计算被旋转的元素的size，看下图：

在LEFT_ROTATE里加入下列两行代码以维护size信息：

y.size = x.size; x.size = x.left.size + x.right.size + 1综上所述，插入元素的两个阶段里，维护size息共需O(lg(n))的时间。

同 样，在删除元素时，同样分为两个阶段，阶段一：从树中删除元素，阶段二，通过旋转维护红黑信息。对于阶段一，我们可以沿着被删除的元素一直向根遍历，经由 的每个结点的size域都减1；在阶段二至多有O(lg(n))次旋转。所以删除操作时维护size域的运行时间同样为O(lg(n))。

如何扩张数据结构

对一种数据结构的扩张过程可分为四个步骤：
１、选择基础数据结构；　（选择红黑树）
２、确定要在基础数据结构中添加哪些信息；　（加入size域）
３、验证可用基础数据结构上的基本修改操作来维护这些新添加的信息；　（插入和删除可以维护size域）
４、设计新的操作。　（OS_SELECT和OS_RANK）

以上给出的是一般模式，不必生硬地遵循。

对于红黑树的扩张，我们可以给出以下概括：
设 域f对含n个结点的红黑树进行扩张的域，且假设某结点x的域f的内容可以仅用结点x，x.left和x.right中的信息计算，包括x.left.f和 x.right.f。这样，在插入和删除操作中，我们可以在不影响这两个操作O(lg(n))渐近性能的情况下，对T的所有结点的f值进行维护。

下面再介绍另一个红黑树的扩张：区间树。

区 间树中，每个结点的关键字不是简单的整数，而是一个区间[low, high]，域名key同样也更名为interval。在进行关键字比较时，low更小的值作为更小的值放在树的左侧。同时，每个结点还维护一个max 域，它表示以该结点为根的子树里，所有元素里的区间[low, high]的high值中的最大值。

我们这样定义两个区间重叠（overlap）：[low, high]和[low', high']只有在high < low'或high' < low时才不重叠。

基于这个数据结构，我们可以定义一个新操作：给定一个区间i，查找区间树中与i重叠的区间：

INTERVAL_SEARCH(T, i) {
1      x = T.root;
2      while x != T.nil and i does not overlap x.interval {
3            if left != T.nil and x.left.max >= i.low
4                  x = x.left;
5           else
6                  x = x.right;
7      }
8      return x;
}