首页 > 其他分享 >FHQ-Treap

FHQ-Treap

时间:2023-07-17 23:33:58浏览次数:34  
标签:左子 val 递归 rnd Treap FHQ

简介

FHQ-Treap 是一种无旋转的 Treap。 和大多数的平衡树不一样,它并不是用旋转来维护的,而是使用了 split(分裂)和 merge(合并)两种操作来维护 Treap 的性质。

实现

split

split 操作可以将一个 FHQ-Treap 按照某个值分裂为两个 FHQ-Treap:

  • 按照权值分:将权值 \(\le val\) 的放到一个 FHQ-Treap 中,\(>val\) 的放到另一个。
  • 按照排名分(之后的变种会用到):将排名 \(\le rank\) 的放到一个 FHQ-Treap 中,\(>rank\) 的放到另一个。

那么如何实现?(以权值分裂,A 为 \(\le val\) 的 FHQ-Treap,B 为 \(>val\) 的 FHQ-Treap):

设我们现在在节点 \(x\) 处,如果 \(val_x\le val\),那么由于二叉搜索树的性质, \(x\) 左子树中的点权肯定满足 \(\le val\),所以我们将 \(x\) 及其左子树加入 A。由于右子树中可能有 \(\le val\) 的点和 \(>val\) 的点,所以我们递归处理右子树。(\(val_x>val\) 同理)

考虑我们如何将 \(x\) 及其左/右子树加入 A/B:

假设我们将 \(x\) 及其左子树加入了 A,然后我们在递归 \(x\) 的右子树发现了第一个节点及其左儿子应该被加入 A,那么我们应该把这部分挂在 A 的哪里呢?

由于二叉搜索树的性质,这个点及其左儿子的权值肯定都大于已经在 A 中 \(x\) 的 \(val_x\)(\(x\) 的左子树不用考虑,因为 \(val_x\) 是 \(x\) 及其左子树中权值最大的一个),那么由于我们只将 \(x\) 及其左子树挂到了 A,而 \(x\) 的右子树是空的,我们找到的第一个节点又是剩余应该被挂入 A 中的节点中最小的那个(因为二叉搜索树的性质,向右子树递归时点权会越来越大),所以我们直接将这个点及其左子树挂到 A 中 \(x\) 的右儿子即可。(且由于深度大小关系不变,另一随机关键字仍满足堆的性质)(另一半同理)如图:

由于每一次递归都会使 \(x\) 的深度+1,而 Treap 的期望深度为 \(\log n\),所以 split 操作是 \(\mathcal{O}(\log n)\)。

在代码实现上,可以将 A 和 B 下一个插入的位置传址到下一个递归中,这样在下一个递归中如果要挂节点直接将传下来的位置设为当前节点即可(注意 pushup,主要是更新 size)。

void split (int root, int v, int &x, int &y) {
   if (! root) {x = y = 0; return ;} if (val[root] <= v) x = root, split (sr[root], v, sr[root], y);
   else y = root, split (sl[root], v, x, sl[root]); pushup (root);
}

merge

合并操作是将两个 FHQ-Treap A 和 B 合并(注意 A 中最大的点权必须小于等于 B 中最小的点权,否则无法合并)。在合并时需要依靠随机关键字 \(rnd\) 来确定树的形态。

假设此时 A 的合并递归到了 \(x\),B 的合并递归到了 \(y\),此时我们考虑:

如果 \(rnd_x<rnd_y\),那么说明 \(y\) 应该被合并在 \(x\) 的下面,而由于 B 中的点权始终大于 A 的点权,所以我们应该将根节点为 \(y\) 的子树和 \(x\) 的右子树合并,所以我们递归合并 \(x\) 的右子树和根节点为 \(y\) 的子树,并将 \(x\) 的右儿子设为合并后新树的根。

如果 \(rnd_x>rnd_y\),那么说明 \(x\) 应该被合并在 \(y\) 的下面,而由于 A 中的点权始终小于 B 的点权,所以我们应该将根节点为 \(x\) 的子树和 \(y\) 的左子树合并,然后递归,设置 \(y\) 的左儿子。

当递归时 \(x\) 或 \(y\) 一方变为空时,那么直接返回另一方即可,如图(黑底白字为 \(val\),白底黑字为 \(rnd\)):

注意不要忘记 pushup。(在代码中若 A 和 B 有一方为空,则直接返回 A+B 的原因是为空即值为 0,相加后的值就是另一方不为 0 的值)

int merge (int A, int B) {
	if (! A || ! B) return A + B; if (rnd[A] < rnd[B]) {sr[A] = merge (sr[A], B); pushup (A); return A;}
	else {sl[B] = merge (A, sl[B]); pushup (B); return B;}
}

标签:左子,val,递归,rnd,Treap,FHQ
From: https://www.cnblogs.com/ClapEcho233/p/17561619.html

相关文章

  • FHQ-Treap的详细图解
    第一部分按值分裂的FHQ-Treap按值分裂的FHQ-Treap的典型例题是P3369【模板】普通平衡树。思路FHQ-Treap是什么?FHQ-Treap是二叉搜索树的一种。比如:FHQ-Treap的思想是什么?分裂->操作->合并下面我们就来慢慢讲这些操作。分裂我们可以根据给定的\(k\)将平衡树分......
  • 旋转Treap树
    #include<bits/stdc++.h>usingnamespacestd;constintM=1e6+10;intcnt=0;//cnt记录当前节点个数,最新一个节点即t[cnt]introot=0;//root是整棵树的树根,初始为空树所以root初始化=0intn;//n表示操作次数structNode{ intls,rs;//左右儿子 intval,pr......
  • 旋转Treap
    splay是通过splay操作均摊复杂度,而旋转treap也旋转,但是是通过随机赋权使得复杂度在期望下正确。具体来说就是再随机赋一个权值\(rank\),通过旋转使得这棵树的\(val\)满足二叉搜索树且\(rank\)满足小根堆。具体来说,在查询的时候是不旋转的,只有在插入和删除时有旋转。......
  • 非旋TREAP
    非旋TREAP目录非旋TREAP一、TREAP—新的树形结构1.treap=tree+heap2.更优秀的时间复杂度3.treap的基础打法1.基本框架-开数组2.动态开点3.sz的维护4.分离和统一4.treap的进阶使用1.treap相比于线段树的好处2.在treap上pushup和pushdown1.总体规则1.在自己做了标记的事后下传标记,......
  • Treap 模板代码
    structNode{ intpri,data,num,sz,ch[2],fa;}t[maxn];intpos;structTreap{ introot; intnewNode(intx){ t[++pos]=(Node){rand(),x,1,1,0,0,0}; returnpos; } voidupdate(intx){ t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+......
  • FHQ-Treap
    模板传送FHQ-Treap顾名思义就是范浩强大佬设计的一种二叉平衡树下面我们来讲一下它的原理和代码结构体对于一个节点,我们需要记录的是对应的值子树节点数左右孩子编号对应的随机值structstr{ intval,size,l,r,key;}fhq[100005];看到这里有人疑惑了,这个对应的随机......
  • treap树
    Treap树  =   tree+heap数和堆的集合,每个节点有值val,也有优先级key,那么这棵树的形态就被确定了,和插入顺序无关了(有赖于优先级避免退化成链:再生成节点时,随机生成优先级,然后插入时动态调整 1、FHQ treap又称无旋treap,没有旋转操作,使用分裂和合并两个操作维护树的平衡......
  • Treap树学习笔记
    等我写完。普通fhqtreap:enum{Maxn=1000005};structFHQTreap{intlson[Maxn],rson[Maxn],data[Maxn];intrnd[Maxn],sze[Maxn],root,tot,seed;FHQTreap(void){Ms(lson,0),Ms(rson,0),Ms(data,0);Ms(rnd,0),......
  • FHQ_Treap 板子
    namespaceFHQ{#definesiz(x)({Node*_a_=x;_a_==np?0:_a_->sz;})structNode{ Node*ls,*rs; charval;intpri; intsz; voidupdsz(){ sz=1+siz(ls)+siz(rs); }}cs[N];voidoutput(Node*root){ if(root==np)return; output(root-......
  • Treap 学习笔记
    一、TreapTreap是一种通过旋转操作维护性质的二叉搜索树。定义详见要维护的东西还是一样,对于每个节点,要维护它的左右儿子,子树大小,还有权值和随机的优先级(这样才能保证树的高度是\(O(\logn)\)级别的)。注意:旋转、分裂、伸展什么的都是手段,维持平衡树的2个性质才是目的。......