首页 > 笔记 > fhq treap总结

fhq treap总结

来一发数据结构

首先Orz fhq %%%%%

何为Treap

Treap是一种二叉平衡树。Treap=BST+Heap

Treap比较好玩的一点是,它整体是拥有二叉搜索树的性质,但是它的每一个节点都会有一个附加权值,它的附加权值是符合堆的性质。

这样我们可以明显看出,这棵树的形态(平衡与否)是由这个附加权值决定的。

那我们该如何取这个权值呢?随机!!

是的,我们每次都随机一个权值作为它的附加权值,那么它就大概是平衡的。

但是一般的平衡树都会有很恼人的旋转,又不好写,又不好调。

这里就郑重推出:fhq treap!

只需要两个基础操作,就可以达到splay的所有功能

1: ¥split¥

GIF

它的主要思想就是把一个Treap分成两个。

split操作有两种类型,一种是按照权值分配,一种是按前k个分配。

第一种就是把所有小于k的权值的节点分到一棵树中,第二种是把前k个分到一个树里。

权值版:

对于我们遍历到每一个点,假如它的权值小于k,那么它的所有左子树,都要分到左边的树里,然后遍历它的右儿子。假如大于k,把它的所有右子树分到右边的树里,遍历左儿子。

因为它的最多操作次数就是一直分到底,效率就是$O(\log n)$。

对于前k个版的,就是像找第k大的感觉。每次减掉siz

2: $merge$

这个就是把两个Treap合成一个,保证第一个的权值小于第二个。

GIF

因为第一个Treap的权值都比较小,我们比较一下它的tar(附加权值),假如第一个的tar小,我们就可以直接保留它的所有左子树,接着把第一个Treap变成它的右儿子。反之,我们可以保留第二棵的所有右子树,指针指向左儿子。

你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树,也可以理解为在第二个树的左子树上插入第一棵树。因为第一棵树都满足小于第二个树,所以就变成了比较tar来确定树的形态。

也就是说,我们其实是遍历了第一个trep的根->最大节点,第二个Treap的根->最小节点,也就是$O(\log n)$

代码:

下面我们就可以通过这两个基本的东西实现各种各样的操作了。

3:$insert$

插入一个权值为v的点,把树按照v的权值split成两个,再按照顺序merge回去。

4: $del$

删除权值为v的点,把树按照v分成两个a,b,再把a按照v-1分成c,d。把c的两个子儿子merge起来,再merge(merge(c,d),b)

5: $precursor$

找前驱的话把root按v-1 split成x,y,在x里面找最大值

6: $successor$

找后继的话把root按v split成x,y,在y里找最小值

7: $rank$

把root按v-1 split成x,y,排名是x的siz

代码:普通平衡树

代码非常短小精悍

那我们该如何操作区间呢?

我们先把root的前r个split出来,再在前面的子树中split前l-1个,然后我们就得到了操作区间

模版:文艺平衡树

再甩一道模版题:bzoj1500


32 COMMENTS

  1. attack2042017-07-11 下午4:11

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    厉害厉害

  2. Magolor2018-01-21 下午2:09

    请问一个问题,FhqTreap如何不按照关键字提取一个特殊点?

    即实现函数Split(x),其中x为传入的这个点的编号(但整棵树不是以编号作为关键字的)

    例如【BZOJ2827 千山鸟飞绝】,需要将一个指定点从当前平衡树中分裂出,并插入到另一棵平衡树中

    • Magolor2018-01-21 下午3:03

      这道题好像明白了,可以按照指定点作为关键字,然后维护区间max就好了……

      但是就这个问题来说,请问怎么解决呢?

      • 远航之曲2018-01-21 下午4:32

        您的意思是知道这个点的下标?那应该可以直接找出值来split吧。。

        • Magolor2018-03-12 上午11:42

          不,就是只知道这个点的指针。
          例如文艺平衡树,如果不要求输出整个序列,而是每次询问i所在的位置(而不是位置i的值)。用Splay是可以做到的,不知道FhqTreap能不能做。

          • 远航之曲2018-03-12 下午8:58

            我以前也想过实现这个。。但是发现这样单独split后再单独merge,关键字就全乱了。。大概是不行的吧。。

    • thchuan20012018-01-24 下午10:17

      CZ!!!
      CZ!!!
      CZ!!!

  3. xxy2018-02-01 上午9:20

    请问文艺平衡树中build函数随机新节点的附加权值,如何保证它满足堆的性质

    • 远航之曲2018-02-01 上午10:02

      这样build出来树的深度是严格logn的,和一个一个插入得出的深度是一样的。其实应该是每次插入一个新点更好一些。。

  4. Fop_zz2018-02-12 下午3:15

    所以说对于维护区间和之类的像线段树一样就行了?

  5. Fop_zz2018-02-12 下午3:43

    文艺平衡树为什么要建到n+2

    • 远航之曲2018-02-13 下午3:01

      其实是新建了两个哨兵节点,作为dfs时候的终止标志。。现在想想好像也不大需要

      • Fop_zz2018-02-14 下午3:48

        好的谢谢

  6. functionendless2018-03-02 上午7:29

    不知道有没有人说过,但那张merge的GIF好像错了
    总树的第二个节点不应该是第二颗子树的吧

    • 远航之曲2018-03-03 上午9:17

      是的那个儿子权值应该是40。。

      还有最后一个9的儿子应该merge在右儿子。。

    • 远航之曲2018-03-03 上午9:18

      当时too young。。

      • sad2018-04-01 下午3:48

        大佬,查询后继 不应该是split(root, a + 1, x, y)吗
        为什么是split(root, a, x, y);

        • 远航之曲2018-04-01 下午6:03

          split(root, a, x, y)以后比a大的数都在y里面,在这里面找最小的就行了啊,不懂你split(root, a + 1, x, y)是什么意思。。

      • sad2018-04-01 下午3:52

        还有有重复元素怎么办啊

        • 远航之曲2018-04-01 下午6:04

          有重复就直接加进去就行,记得上面写成<=就好了

          • sad2018-04-03 下午3:17

            大佬我的意思是文艺平衡树,84到85行,反转出来的区间不是(l + 1, r + 1)吗
            应该不对吧

  7. %%yzy2018-04-07 上午10:49

    大佬能不能详细解释del操作,蒟蒻看不懂...

    • %%yzy2018-04-07 上午10:59

      "把c的两个子儿子merge起来"这一步是不是有些多余

      • %%yzy2018-04-07 上午11:14

        哦懂了,题目吗没看清以为删光所有值为v的...

  8. Mocha2018-04-16 下午4:32

    楼上sad的关于文艺平衡树84,85行的问题,同问。。(弱

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×