14. 数据结构的扩张

一些工程应用需要的只是教科书中的标准数据结构，也有许多其他的应用需要对现有数据结构进行少许的创新和改造，但只有很少的情况需要创造全新类型的数据结构。
更经常的是，通过存储额外信息的方法来扩张标准的数据结构，然后对这种数据结构编写新的操作来支持所需要的应用。

比如：

动态顺序统计量

之前我们讨论了中位数和顺序统计量，对于一个无序的集合，我们可以在$\Omicron(n)$的时间内确认任何顺序统计量。这里我们将介绍如何修改红黑树，使得可以在$\Omicron(\lg n)$时间内确认任何的顺序统计量。以及如何在O(lgn)时间内得到一个元素的秩，即它在集合线性序中的位置。

下图展示了一种支持快速顺序统计的数据结构，顺序统计树。这种数据结构是在红黑树的基础上，给每个元素添加一个属性size。一个结点的size表示以这个结点为根结点的子树大小。我们定义哨兵T.nil的size为0，则有如下等式

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

查看给定秩的元素

从根结点开始查找，首先通过左孩子的size+1得到当前结点为根节点时的秩r，然后和需要查找的秩i作比较。如果相等则直接返回，如果i < r 查看左孩子，否则递归查看右孩子，但是查看右孩子时，需要传入i - r，因为右子树并不能知道左子树的大小，而右孩子实际的轶为r+右孩子为根结点时的右孩子的秩：

RANK(x.right) = RANK(x) + (x.right.left.size + 1)

查看一个元素的秩

假如一个元素x的父结点为根结点，
当这个元素x是根结点的左孩子时，$RANK(x) = x.left.size + 1$
当这个元素x是根结点的右孩子时，$RANK(x) = RANK(x.p) + x.left.size + 1$

利用上面的性质，求解一个元素x的秩时，我们循环的求解当x的父结点为根结点时，x在这个子树中的大小，每次循环上移一层，直到移动到真实的root结点，这时我们已经求出了该元素真实的秩。

维护size

当插入/删除元素时，除了维护红黑树的特性，我们还要维护结点的size属性。正常的插入/删除导致的size变化比较简单，不在赘述。我们看看当发生旋转时size的维护：

当对x做左旋后，我们需要重新计算x的size，并且把x之前的size赋给y，因为旋转不会影响这个局部子树的size。
当对y做右旋后，我们需要重新计算y的size，同理把y之前的size赋给x。

如何扩张数据结构

扩张一种数据结构可以分为4个步骤：

1. 选择一种基础数据结构
2. 确定基础数据结构中要维护的附加信息
3. 检验基础数据结构上的基本修改操作能否维护附加信息
4. 设计一些新操作

在扩张数据结构时，不一定非得时上述结构，上述只是一个一般模式。但我们可以把上述步骤作为一个check list来检验扩张数据结构是否完善。

区间树

有些问题可能会涉及到区间数据，这时候可能就需要用到区间树。比如：查看某一时间段内发生的事。

我们把一个区间[l, h]表示成一个对象i，i.low = l为低端点，i.high = h为高端点。
下图展示了两个区间的三种状态：

• a，区间i和区间i’重叠
• b，区间i在区间i’的左边（i.h < i’.l）
• c，区间i在区间i’的右边（i.l > i’.h）

区间树是一种对红黑树扩展的数据结构，我们看看红黑树扩展为区间树的过程：

1. 基础数据结构
   选择红黑树，每个元素包含区间属性x.int，x的key为x.int.low。
2. 附加信息
   每个结点除了区间信息外，包含一个值x.max，它表示以x为根结点子树中所有端点的最大值。
3. 对信息的维护
   在插入/删除操作后，需要对max值做维护，最多影响树高h个元素的max值，而且每次维护只需要常数次操作。所以不会影响原有操作的时间复杂度。

   x.max = max(x.int.high, x.left.max, x.right.max)

4. 设计新的操作
   新操作INTERVAL-SEARCH(T, i)，用来查找区间树T中与区间i重叠的结点。若树中没有区间与i重叠，则返回T.nil。

INTERVAL-SEARCH(T, i)：将x指向root结点开始循环查看x是否与i重叠，如果重叠则退出循环返回x。如果x有左孩子且左孩子的max值大于等于i.low，则循环查看x的左孩子，否则循环查看x的右结点。

TODO: 用循环不变式证明各个扩张的正确性