FHQ

FHQ是一种非旋Treap。没有了复杂的左/右旋操作所以十分适合菜鸡。

其保证复杂度的方法和Treap一样:给每一节点一个随机权记为\(rad[i]\),然后使平衡树满足是关于\(rad[i]\)的堆。构建二差搜索树时,树的形态唯一而且期望深度为\((logn)\)

*复杂度小证明:

这个思路来自于[一篇博客](关于非旋FHQ Treap的复杂度证明 - 谁是鸽王 - 博客园 (cnblogs.com))

(默认是大根堆)

将节点编号\((i)\)按题中数据(记为\(val[i]\))从小到大排序得到序列\(A\)

将节点编号按\(rad[i]\)从小到大排序得到序列\(B\)

发现\(A\)、\(B\)有如下性质:1、A就是这棵树的中序遍历。2、B的最后一个数是所有其他的祖宗(根)。

那么这棵树的形态如何确定?显然这是一道普及的题。

\(B\)中取最后一个数\(root\),然后在\(A\)中找到\(root\)。显然\(root\)左边是其左子树右边是其右子树。从\(B\)中挑出左右子树然后递归即可。

显然递归深度就是平衡树深度。

考虑这个过程的本质。对于\(B\)来说就是找到最后一个数\(root\),然后把\(val[i]\)小于\(val[root]\)的放在一边,大于的放在另一边,然后递归。

这不就是快速排序吗?只是参考点为最后一个罢了。由于\(rad[i]\)是随机值所以B序列是随机的。好的,快排对于随机数据的期望复杂度是\(O(nlogn)\)(递归期望深度为\(logn\)),所以由此法构建的平衡树期望深度为\(logn\)。仔细思考构建过程发现平衡树的形态也是唯一的。

代码

FHQ是怎么维护的呢?

FHQ的维护基于两个操作:merge、split。merge负责把两棵树合并。split负责把一棵树裂开,裂成一边小于(小于等于)a,一边大于等于(大于)a。

#includ<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<cstdlib>#include<ctime>using namespace std;#define N 101001int tot,size[N],ch[N][2],rad[N],val[N],root;int new_node(int x){int now=++tot;rad[now]=rand();val[now]=x;size[now]=1;return now;}void update(int now){size[now]=size[ch[now][1]]+size[ch[now][0]]+1;}int merge(int x,int y){if(!x||!y)return x+y;if(rad[x]>rad[y]){ch[x][1]=merge(ch[x][1],y);update(x);return x;}else {ch[y][0]=merge(x,ch[y][0]);update(y);return y;}}void split(int &x,int &y,int now,int w){if(!now){x=y=0;return;}if(val[now]<=w){x=now;split(ch[x][1],y,ch[now][1],w);}else{y=now;split(x,ch[y][0],ch[now][0],w);}update(now);}int kth(int now,int k){int l=ch[now][0];if(size[l]>=k)return kth(l,k);else if(size[l]+1==k)return now;else return kth(ch[now][1],k-size[l]-1);}int read(){int sum=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return sum*f;}int main(){srand(time(NULL));int T=read();while(T--){int type=read();int a=read();int x,y,z;if(type==1){split(x,y,root,a);root=merge(merge(x,new_node(a)),y);}if(type==2){split(x,z,root,a);split(x,y,x,a-1);y=merge(ch[y][0],ch[y][1]);root=merge(merge(x,y),z);}if(type==3){split(x,y,root,a-1);printf("%d\n",size[x]+1);root=merge(x,y);}if(type==4)printf("%d\n",val[kth(root,a)]);if(type==5){split(x,y,root,a-1);printf("%d\n",val[kth(x,size[x])]);root=merge(x,y);}if(type==6){split(x,y,root,a);printf("%d\n",val[kth(y,1)]);root=merge(x,y);}}return 0;} 

普通treap也提一下

插入操作:按普通的二叉搜索树来插,然后回溯时看到不符合堆的性质就把大的旋上来。

删除操作:找到待删点然后把它旋到叶子,然后删除就好了。