FHQ Treap 详解

鲜花一些鲜花放在前面,平衡树学了很久 , 但是每学一遍都忘,原因就在于我只能 70% 理解 + 30% 背板子,所以每次都忘 。这次我采取了截然不同的策略,自己按照自己的理解打一遍 , 大获成功(?),大概打 20 min,调 10 min 结束,然后写下了这篇文章 。
【FHQ Treap 详解】虽然但是,感觉 Treap 还是很强的 , 代码好写好调,而且可以解决很多问题(下面将会提到),好像说是常数大一点?无伤大雅吧……
Treap首先 , 从 Treap 的定义开始 。Treap 实际上是一种笛卡尔树(笛卡尔树可以看 这篇文章,每个点有两个信息 \((v_u,p_u)\),分别表示点 \(u\) 的权值与优先度 。\(v_u\) 形成一个二叉搜索树(左儿子的值 \(\leq\) 自己的值 \(\leq\) 右儿子的值) , \(p_u\) 形成一个大根堆(自己的值 \(\geq\) 左右儿子的值) 。
你可以利用 Treap 做很多有用的操作,但是 Treap 有一个缺点,就是如果被卡成链怎么办?
FHQ Treap这时候就需要用到 FHQ Treap , 它基于 Treap 的基础上对每个点的 \(p\) 值都进行了随机化操作,这样就可以达到平衡的目的了 。为什么?因为随机出来不平衡的概率很小 , 大多随机数都是无规律的,这样通过大根堆的性质就可以使它达到平衡,这样树高期望就是 \(O(\log n)\) 层的了,并且无法卡掉,因为随机数是程序生成的,并非数据所决定 。

系统随机函数若以 srand(time(0)) 为随机种子,效果不佳,推荐使用 mt19937 rnd(233),生成随机数更加均匀 。
FHQ Treap 又叫无旋 Treap,它只需要两个核心操作 merge()split() 即可完成所有的复杂操作,就像玩拼图一样把一棵树拆开再拼起来一样 。下面就来具体介绍一下这两个函数到底是如何实现的 。
关于 upd 函数的说明
(这个可以学完下面的再看)upd 函数,即刷新一个节点大小的函数 。在 split() 中,在分裂完子树后最后应该刷新,不然可能大小信息已经被更改而不知道 。同理,在 merge() 中,合并子树后也应当刷新,调不出来一定要检查一下是否因忘记刷新而错误 。
split 函数split 函数实现的功能是把一棵树按照权值大小拆分成两棵树 , 具体来说,split(int cur,int k,int &x,int &y) 表示将以 cur 为根的子树拆分成两棵树 \(x\) 和 \(y\),其中 \(x\) 里的权值都 \(\leq k\),\(y\) 里的权值都 \(>k\) 。
怎么写呢?首先,为了方便返回,直接将要拆分成的两棵子树引用定义在函数参数中 。先特判一下,如果要拆分的树为空 , 则拆分出来的两棵树也为空 。不然就判断树根是否 \(\leq k\),如果是,则树左子树都 \(\leq k\),即属于 \(x\),那么只要分裂右子树即可,反之亦然 。
代码void split(int cur,int k,int &x,int &y){if(!cur){x=y=0;return;}if(tree[cur].val<=k){x=cur;split(tree[x].rs,k,tree[x].rs,y);}else{y=cur;split(tree[y].ls,k,x,tree[y].ls);}upd(cur);}
merge 函数merge 函数就是把两个树 \(x,y\) 合并,保证所有 \(x\) 中的 \(v\) 都 \(\leq\) 所有 \(y\) 中的 \(v\),具体来说,就是 int merge(int x,int y)
写法就是判断 \(x,y\) 中是否有空树 , 有的话直接返回另一个即可 。不然比较两者根的有先值,如果第一个大,根据大根堆性质,显然应该合并 \(x\) 的右子树和 \(y\),反之亦然 。
代码int merge(int x,int y){if(!x||!y)return x+y;if(tree[x].key>=tree[y].key){tree[x].rs=merge(tree[x].rs,y);upd(x);return x;}else{tree[y].ls=merge(x,tree[y].ls);upd(y);return y;}}
其他操作的实现下面来看看 FHQ Treap 能实现哪些操作吧 , 请看模板题 普通平衡树 。(下面全部内容为笔者自己发挥,若有更好做法请在评论区留言或私信笔者)
插入 \(x\):将根以 \(x\) 值分裂,在中间建一个新的点合并回去即可,比较容易 。删除 \(x\):将根分别以 \(x-1,x\) 分裂,中间一个树就是权值为 \(x\) 的树,把这个树替换为它左右子树合并的结果即可(因为只要删一个,相当于把根节点给删了 。查询 \(x\) 的排名:这个非常容易,直接按 \(x-1\) 分裂并输出第一个子树大小 +1 即可 。查询排名为 \(x\) 的数:这个可以从根节点开始,不停地判断应该往左子树走还是右子树走,判断方式就是看当前点地左子树大小 +1 和 \(x\) 的大小关系,若相等则直接退出 。**查询 \(x\) 的前驱:$$笔者做法比较暴力 , 直接将数按 \(x-1\) 分裂,第一棵树的最后一个就是 , 最后一个求可以查询排名为数大小的数,用之前的函数可以求出 。**查询 \(x\) 的后继:$$同前驱做法,按 \(x\) 分裂,第二棵树的第一个就是,同样查询排名为 1 的树即可,使用之前的函数 。

推荐阅读