首页 > 其他 > 详细

平衡树(三)——FHQ Treap

时间:2021-06-12 01:12:41      阅读:17      评论:0      收藏:0      [点我收藏+]

前言

上文介绍了普通的平衡树,它简单(奇怪,鬼畜)的旋转操作确实死难写也难调(刚写挂一个),于是跑去学了一个不用旋转的平衡树,无旋 \(Treap (FHQ~~Treap)\)

只需要两个操作达到 \(splay\) 全部功能 ?? 太炫酷了

概况

\(FHQ~~Treap\) 和普通的 \(Treap\) 一样每个节点维护两个值,一个是权值,一个是随机值

但是它不再是用旋转来维护,而是通过 \(split\)\(merge\) 进行维护

操作

split(分树)

把一个 \(Treap\) 分成两个

两种:按权值分,按子树大小分

复杂度 \(O(log n)\)

按权值分

把权值小于 \(k\) 的节点都分到一棵树中,其余的点都分到另一棵树中

如果当前节点权值小于 \(k\) 那么它的左子树都会分到一棵树内,然后向右孩子查找

否则该节点的右节点都会分到另一个子树内,然后向右查找

    void split(int p, int k, int &x, int &y) {
        if (!p) x = y = 0;
        else {
            if (val[p] <= k) x = p, split(rs(p), k, rs(p), y);
            else y = p, split(ls(p), k, x, ls(p));
            update(p);
        }
    }

按子树大小分

把一棵树分成两棵树,其中一棵的大小为 \(k\)

\(Treap\)\(Kth\) 操作类似

如果当前点的左子树大小大于 \(k\) ,向左子树继续查找

否则的话该点的左子树一定在大小为 \(k\) 的树中,然后使右子树分出 \(k - siz[p] - 1\) 大小的子树

    int split(int p, int k, int &x, int &y) {
       if(!p) x = y = 0;
       else {
          if(k <= siz(ls(p)))
            y = p, split(ls(p), k, x, ls(p));
          else 
            x = p, split(rs(p), k - siz[ls(p)] - 1, rs(p), y);
          update(p);
       }
    }

merge(合并)

先咕着,明天写……

平衡树(三)——FHQ Treap

原文:https://www.cnblogs.com/Arielzz/p/14876741.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!