順序統計樹

在計算機科學，順序統計樹（英語：Order statistic tree）是二叉搜索樹的變種。除了插入、查詢和刪除，這種數據結構還支持以下兩種操作：

• 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樹, 維護節點顏色能實現紅黑樹）。 直接使用節點大小的信息，也能實現加權平衡樹。