顺序统计树

通过修改红黑树，使得可以在O(lgn)时间内确定任何的顺序统计量

顺序统计树T只是简单的在每个节点上存储附加信息的一棵红黑树，在红黑树的节点x中，除了通常属性x.key,x.color,x.p,x.left,x.right之外，还包括一个属性x.size，这个属性表示以x为根的子树的节点数，即这棵树的大小。

T.nil.size = 0
x.size = x.left.size + x.right.size + 1

返回以x为根的子树中包含第i小关键字的节点伪代码OS-SELECT(T.root,i)

OS-SELECT(x,i)
r = x.left.size + 1
if i == r
        return x
elseif i < r
        return OS-SELCT(x.left,i)
else
        return OS-SELCT(x.right,i-r)

确定一个元素的秩
给定指向顺序统计树T中节点x的指针，过程OS-RANK返回对T中序遍历对应的线性序列中x的位置

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.size + 1
        y = y.p
return r