查看“︁顺序统计树”︁的源代码

在[[计算机科学]]，'''顺序统计树'''（{{lang-en|Order statistic tree}}）是[[二叉搜索树]]的变种。除了插入、查询和删除，这种数据结构还支持以下两种操作：

* [[选择算法|Select(''i'')]] — 在树中查询第''i''小的元素
* Rank(''x'') – 查找元素''x''的排名

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

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

<syntaxhighlight lang=c>
size[x] = size[left[x]] + size[right[x]] + 1;
</syntaxhighlight>

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

<syntaxhighlight lang=c++>
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);
}
</syntaxhighlight>

Rank操作实现如下：

<syntaxhighlight lang=c++>
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;
    }
}
</syntaxhighlight>

通过改进顺序统计树，能够实现其他数据结构（例如, 维护节点的高度能实现[[AVL树]], 维护节点颜色能实现[[红黑树]]）。 直接使用节点大小的信息，也能实现[[加权平衡树]]。<ref>{{Cite conference|doi=10.1007/3-540-48224-5_39|title=A new method for balancing binary search trees|conference=[[ICALP]]|volume=2076|pages=469–480|series=Lecture Notes in Computer Science|year=2001|last1=Roura|first1=Salvador|isbn=978-3-540-42287-7}}</ref>

== 参考文献 ==
{{reflist|30em}}

{{计算机科学中的树}}

[[Category:树结构]]
[[Category:选择算法]]