前言：通常我们会遇到一些问题，采用一些标准的数据结构，如双链表、散列表或二叉查找数时，不能够满足操作要求，需要对这些数据结构进行扩张，添加一些额外的信息使得能够完成新的操作。附加的信息需要对数据结构的某些操作进行调整，这个是非常关键的步骤，决定着数据结构扩张是否能够实现。本章主要讨论了红黑树结构的扩张，介绍了两种扩张方式。第一种方式扩张使得红黑色能够支持动态集合上顺序统计，快速找出集合中第i小的数，或给出某个元素在集合的全序中的排名。第二种方式扩张使得红黑色能够进行区间操作，可以很快地找到集合中覆盖的区间。关于红黑色请参考第13章，。

1、动态顺序统计

　　在第九章介绍了顺序统计的概念，大概的意思是在包含有n个元素的集合中，第i个顺序统计量指的是该集合中第i小的元素。在一个无序的集合中，任意顺序统计量都可以在O(n)时间内找到，详细情况可以参考。书中在此基础上修改红黑树的结构，使得任意的顺序统计量都可以再O(lgn)时间内确定。向红黑树的结构中添加一个size域，表示包含自身节点的当前节点的子树节点的数目。这样修改后可以快速支持顺序统计量操作，将这种修改后的红黑树叫做：顺序统计量树T。修改后的结构如下所示：

struct RBTreeNode{   int key;   int color;   struct RBTreeNode *parent;   struct RBTreeNode *left;   struct RBTreeNode *right;   int size;  };

例如给定红黑树的一个节点x，则size[x] = size[left[x]]+size[right[x]]+1。size[x]为包含以x为根的子树的节点数（包含x本身），即子树的大小。如果哨兵定义为0，即设置size[nil[T]]=0。

下面给出一个修改后的红黑树的例子，如下图所示：

　　红黑树是二叉排序树，按照中序遍历从小到大输出红黑树中的关键字。从图中可以看出，添加size域后，很方便看出每个节点的子树的节点数目（包含自身节点）。书中在后面讨论这种结构的操作，分别讨论如下：

（1）检索具有给定排序的元素

　　过程OS_SELECT(x,i)返回一个指向以x为根的子树中包含第小关键字的结点的指针，即为了找出顺序统计量树T中的第i小关键字，可以调用OS_SELECT(root[T],i)。书中给出了伪代码如下：

OS_SELECT(x,i)    r = size[left[x]]+1; //先计算x的处于的位置    if i = r         //x正好是第i小的关键字        then return x;    else if i < r   //x比第i关键字大，则在其左子树查找        then return OS_SELECT(left[x],i)    else return OS_SELECT(right[x],i-r)  //x比第i关键字小，则在其右子树查找

　　该过程类似二分查找，每一次递归调用都在顺序统计数中下降一层，故最坏情况下OS_SELECT的总时间与树的高度成正比，红黑树的高度为lgn。故OS_SELECT的运行时间为：O(lgn)。

（2）确定一个元素的秩（位置）

　　给定指向一顺序统计树T中节点x的指针，求x在顺序统计树中序遍历得到的线性序中的位置。书中给出了OS_RANK(T,x)过程的伪代码：

OS_RANK(T,x)    r = size[left[x]]+1;   //获取以x为根子树中x的位置（中序遍历）    y = x;    while y != root[T]    //从下向上直到根节点          do if y = right[p[y]]   //如果是右子树                  then  r = r + size[left[p[y]]]+1;           y = p[y]; //向上移动    return r;

从程序总可以看出当y == root[T]时候循环终止，此时以y为根的子树是课完整树，此时r值是这颗整树中key[x]的秩。while循环中的每一次迭代花O(1)时间，且y在每次迭代中沿树上升一层，故在最坏情况下0S_RANK的运行时间与树的高度成正比：对含n个节点的顺序统计树时间为O(lgn)。

（3）对子树规模的维护

　　在红黑树中添加size域后，能够通过OS_SELECT和OS_RANK迅速计算出所需的顺序统信息。通过修改红黑树的插入和删除操作，在此过程是通过旋转来修改size域。关于这部分需要在红黑树的基础上进行改进，比较复杂，暂时没有实现。

2、如何扩张数据结构

对一种数据结构的扩张过程分为四个步骤：

1）选择基础数据结构

2）确定要在基础数据结构中添加哪些信息

3）验证可用基础数据结构上的基本修改操作来维护这些新添加的信息

4）设计新的操作

　　书中给出了对红黑树进行扩张的定理，并给出了证明，这个看的时候有些难度，暂时跳过了。大概意思就是说当红黑树被选作基础数据结构时，某些类型的附加信息总是可以用插入和删除来进行有效地维护。

3、区间树

　　这小结讲的是扩张红黑树以支持由区间构成的动态集合上的操作。区间可以很方便的表示各占用一段连续时间的一些事情。区间树是一种动态集合进行维护的红黑树，该集合中的每个元素x都包含在一个区间int[x]。区间树支持下列操作：

INTERVAL_INSERT(T,x)：将包含区间域int的元素x插入到区间树T中

INTERVAL_DELETE(T,X)：从区间树T中删除元素x

INTERVAL_SEARCH(T,i)：返回一个指向区间树T中元素x的指针，使int[x]与i重叠，若集合中无此元素存在，则返回nil[T]。

修改红黑树得到的区间树如下图所示：

从图可以看出，对区间树以每个节点的左端点值进行中序变量即可得到有序的序列。有了区间树的结果就很容易实现其相关操作。