第十四章 数据结构的扩张
总结：这一章对红黑树进行扩张，介绍了顺序统计树和区间树。
1. 动态顺序统计
顺序统计树：对红黑树中的每个节点都添加了一个域size[x]，代表以节点x为根的子树的节点数（包含x）
size[x]=size[left[x]]+size[right[x]]+1
检索具有给定排序的元素：找出T中的第i个小的元素，调用OS-SELECT(T,i)
伪代码
OS-SELECT(x,i)
r <- size[left[x]]+1
if r=i
then return x
else if i<r
then return OS-SELECT(left[x],i)
else return OS-SELECT(right[x],i-r)
确定一个元素的秩：返回对T进行中序遍历后得到的线性序中x的位置。
伪代码
OS-RANK(T,x)
r <- size[left[x]]+1
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
对子树规模的维护：对红黑树进行扩张后，插入操作、删除操作、左旋、右旋都要进行相应的修改。但是维护后，插入操作、删除操作的复杂度仍为O(lgn)，旋转的复杂度仍为O(1)
插入：第一阶段RB-INSERT()，插入一个节点z后，对从根到z的路径上经过的节点的size都要加1。
删除：第一阶段RB-DELETE()，删除一个节点z，对由z至根的路径上经过的节点的size都要减1。
左旋：对LEFT-ROTATE(T,x)增加以下代码：
size[y] <- size[x]
size[x] <- size[left[x]]+size[right[x]]+1
2. 如何扩张数据结构
1） 选择基础数据结构
2） 确定要在基础数据结构中添加哪些信息
3） 验证可用基础数据结构上的基本修改操作来维护这些新添加的信息
4） 设计新的操作
3. 区间树
区间树是一种对动态集合进行维护的红黑树，集合中的每个元素x都包含一个区间int[x]。x的关键字为区间的低端点low[int[x]]。x中还包含一个新的域max[x]，表示以x为根的子树中所有区间的端点的最大值。
max[x]=max(high[int[x]],max[left[x]],max[right[x]])
找出树T中覆盖区间i的那个节点：
伪代码
INTERVAL-SEARCH(T,i)
x <- root[T]
while x!=NIL and i does not overlap int[x]
do if left[x]!=NIL and max[left[x]]>=low[i]
then x <- left[x]
else x <- right[x]
return x