计算机科学

首页 > 计算机科学

顺序统计树

2018-08-27 10:40:20     所属分类:树结构

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

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

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

算法实现

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

sizex = sizeleftx + sizerightx + 1;

根据定义,树为空时,其大小为0sizenil = 0。Select操作实现如下:

void Select(int t, int i) {
    if (i == sizeleftt + 1) return keyt;
    if (i < sizeleftt) return Select(leftt, i);
    else return Select(rightt, i - sizeleftt - 1);
}

Rank操作实现如下:

void Rank(int root, int x) {
    int rank = sizeleftx + 1;
    for (y = x; ; y = parenty) {
        if (keyy < keyx)
            rank += sizelefty + 1;
        if (y == root) break;
    }
}

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

参考文献

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

上一篇:系统发生树
下一篇:四叉树
相关推荐