计算机科学

首页 > 计算机科学

顺序统计树

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. 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339723.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


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