dwjshift's Blog

用merge和split实现的treap

| Comments

原文发表时间:2014-02-18
本文介绍用merge(合并)和split(分离)来实现各种操作的treap。好处?就是可以跟splay一样玩序列操作,而且还能方便的实现持久化。合起来说嘛,就是能拿一个持久化序列操作的专利。 其实直接暴力改节点的优先级然后旋到根就和splay一样了,不过还要把优先级改回来然后旋回来。另外AVL好像也可以玩持久化序列操作。

merge就是把两棵treap合并成一棵(要求其中一棵的所有元素小于另一棵的)。
split是把一棵treap的前若干个元素分离出来作为一棵treap,剩余的作为一棵treap。

操作的实现

插入就先把待插入的元素建成一棵treap(如果是单个元素就直接新建节点,多个的话用merge合起来),然后从插入的位置split开得到两棵treap,把3棵treap依次merge即可。另外fhq在WC2012的讲稿还有讲另一种不用旋转也不用merge/split的写法。
删除的话用2次split分成3棵treap,然后把第一棵和第三棵merge
直接用两次split就能提取一段。

另外说一下,这样实现的treap基本上每次操作都要用几次的merge/split,所以常数有点大。如果时限卡太紧的话就只能用码长换时间了吧……(大雾

接着详细地讲一下mergesplit怎么做。是随机的优先级,是左右儿子,是该节点的子树包含的元素个数。

merge

merge(x,y)就是把合并,的所有元素小于的。
如果有一个是空的返回另一个就好了。
由于元素大小已知,要么是作为的左儿子,要么就是作为的右儿子,只需要根据随机优先级判断即可。
我的是小根堆。若,那么改为merge(rc[x],y),返回;否则改为merge(x,lc[y]),返回merge应该挺好理解吧……

split

split(now,x,y,k)是把里的前个元素切出来放在,剩余的放在的所有元素小于的。我一开始的时候没想明白要怎么切,比如下面这幅图


我要切前5个元素,切出来的应该是红圈里的。但是它们不是连在一起的怎么破!然后我发现我智商下线了。谁告诉你只能切一刀了?切两刀然后接在一起不就好了么……所以可以这样写:
如果为NULL就把都改成NULL,然后退出。
就把改成,然后split(lc[now],x,lc[y],k);若就把放到,其余的放到;若就把改成,然后split(rc[now],rc[x],y,k-s[lc[now]]-1)
也可以加多一个判断:如果,就把改成改成NULL,然后退出。这样会快一点。
还是用上面的例子看一看整个split的流程吧,上面的是原来的treap,下面的两棵是分离后的结果,紫色箭头指着的是当前处理到哪一个节点,数字表示要切多少个元素。




最后得到的就是这样的:

如果要实现持久化的话,只需要把所有修改节点信息的操作改成新建节点就行了。

参考资料

范浩强 WC2012讲稿 《谈谈各种数据结构》
范浩强 网易博客 《挖掘treap的潜力》
陈立杰 国家集训队作业 《可持久化数据结构研究》
orz以上两位神犇!

Comments

comments powered by Disqus