顺序统计树

维基百科,自由的百科全书

计算机科学顺序统计树(英语:Order statistic tree)是二叉搜索树的变种。除了插入、查询和删除,这种数据结构还支持以下两种操作:

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

这两种操作的平均时间复杂度是。当所用数据结构是平衡二叉树时,这是最坏复杂度。

算法实现[编辑]

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

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]

参考文献[编辑]

  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.