顺序统计树

在计算机科学, 顺序统计树是二叉搜索树的变种。除了插入、查询和删除，这种数据结构还支持以下两种操作：

Select(i) — 在树中查询第i小的元素
Rank(x) – 查找元素x的排名

这两种操作的平均时间复杂度是 $O(\log n)$ 。当所用数据结构是平衡二叉树时，这是最坏复杂度。

算法实现

对于树中的每个节点，需要额外维护以这个节点为根的子树大小（该节点下点的个数）。

size[x] = size[left[x]] + size[right[x]] + 1;

根据定义，树为空时，其大小为0size[nil] = 0。Select操作实现如下：

int Select(int t, int i) {
    if (i == size[left[t]] + 1) return key[t];
    if (i <= size[left[t]]) return Select(left[t], i);
    else return Select(right[t], i - size[left[t]] - 1);
}

Rank操作实现如下：

void Rank(int root, int x) {
    int rank = size[left[x]] + 1;
    for (y = x; ; y = parent[y]) {
        if (key[y] < key[x])
            rank += size[left[y]] + 1;
        if (y == root) break;
    }
}

通过改进顺序统计树，能够实现其他数据结构（例如, 维护节点的高度能实现AVL树, 维护节点颜色能实现红黑树）。直接使用节点大小的信息，也能实现加权平衡树。^[1]

参考文献

^ Roura, Salvador. A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science 2076: 469–480. 2001. ISBN 978-3-540-42287-7. doi:10.1007/3-540-48224-5_39.

[1] Roura, Salvador. A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science 2076: 469–480. 2001. ISBN 978-3-540-42287-7. doi:10.1007/3-540-48224-5_39.

[1]