在OS-SELECT或OS-RANK中,注意到无论什么时候引用节点的size属性都是为了计算一个秩。相应地,假设每个节点都存储它在以自己为根的子树中的秩。试说明在插入和删除时,如何维护这个信息。(注意,这两种操作都可能引起旋转。)
OS-SELECT(root[T], i) r = size[left[x]] + 1 if r == i return x else i < r return OS-SELECT(left[x], i) return OS-SELECT(right[x], i-r) OS-RANK(T,x) r = size[left[x]] + 1 y = x while y!=root[T] if y == right[p[y]] r = r + size[left[p[y]]] + 1 y = p[y] return r