图解无旋Treap/FHQ-Treap
Fume_shroom · · 算法·理论
前言
无旋 Treap，下称 FHQ-Treap。这是一种没有树旋转，码量小且常数不大的一种平衡树。
前置知识：
-
普通二叉搜索树即其会被卡的原因
-
二叉堆
Treap 思想
注意到 Treap
首先我们知道在原数据有序的情况下，树会变成一条链，树高为
其次我们还知道二叉堆是一棵完全二叉树，树高一直是
所以理论上我们在每一个节点插入时赋予其一个随机的权值，在插入的时候让其既满足堆又满足二叉搜索树就可以实现不会被卡的二叉搜索树。
分裂与合并
这两个操作是 FHQ-Treap 的核心，虽然题目一般不会让你直接分裂或合并平衡树，但是 FHQ-Treap 的一些关键操作都依赖于把平衡树分裂与合并。
分裂
顾名思义，即把一棵平衡树的子树分裂成两部分。常见的分裂操作一般是按
设当前需要分裂的子树根节点为
我们分情况讨论一下。
第一种情况：
这种情况下的分裂步骤如下：
- 将
x 的左子树分裂成\le key 和> key 的两部分，设返回值为(a_0,b_0) 。 -
- 返回
(a_0,x) ，即两个部分的根节点，为其父节点（如果有）提供信息。
这种情况的例图：
第二种情况：
这种情况下的分裂步骤如下：
- 将
x 的右子树分裂成\le key 和> key 的两部分，设返回值为(a_0,b_0) 。 -
- 返回
(x,b_0) ，即两个部分的根节点，为其父节点（如果有）提供信息。
这种情况和上一种类似，就不画例图了。
合并
设当前合并的两个子树的根节点分别为
此函数返回合并后的根。
分类讨论解决。
首先是最简单的情况：
然后是其他情况，因为是个 Treap，并且实际上最终根节点是其中的哪一个都可以，所以需要按照随机的
例图：
其他操作
插入
- 在整棵树中分裂
\le x-1 和> x-1 的两部分。 - 在
> x-1 即\ge x 的部分中分裂=x 的和>x 的。 - 如果存在
=x 的部分，就把其cnt 加1 ；否则就创建新节点并初始化。 - 合并过程中所有分裂的部分。
删除
和插入类似，只是把
如果此节点
否则直接合并除了
查询排名，第 k 小，前驱，后继
和普通二叉搜索树一样。
代码
代码不短，建议食用完上述教程后阅读代码来熟悉实现。
//FHQ-treap
#include <bits/stdc++.h>
#define int long long
const int inf=1e9;
using namespace std;
struct node{//树节点
int l=0,r=0,siz,val,pri,cnt;//分别为：左孩子，右孩子 ，子树大小，存储的值，随机优先级，存储的值的数量
}T[100005];//树本体
int root,tot;//树的根与大小
void up(int x){//更新节点x的信息
if(x<1||x>tot) return;//无效
T[x].siz=T[T[x].l].siz+T[T[x].r].siz+T[x].cnt;//更新大小
}
pair<int,int> split(int x,int key){//在以x为根的子树内按小于等于key和大于key分裂成两棵平衡树，返回这两棵树的根（小的在前，大的在后）
if(x==0){//判断是否为0
return {0,0};//无效
}
if(key<T[x].val){//key是否在左边
pair<int,int> tmp=split(T[x].l,key);//左子树的分裂
T[x].l=tmp.second;//左子树中大于key的归为x的左子树，另一部分独立
up(x);//更新x
return {tmp.first,x};//分别返回小于等于key和大于key的子树的根
}
else{//key在右边
pair<int,int> tmp=split(T[x].r,key);//右子树的分裂
T[x].r=tmp.first;//右子树中小于key的归为x的右子树，另一部分独立
up(x);//更新x
return {x,tmp.second};//分别返回小于等于key和大于key的子树的根
}
}
int merge(int x,int y){//合并子树x和子树y，返回合并后的根（要求x内元素小于y内元素）
if(x==0&&y==0) return 0;//情况1：都是0，无需合并，根是0
if(x!=0&&y==0) return x;//情况2：一个是0一个不是0，无需合并，根是其中非0的
if(x==0&&y!=0) return y;//同情况2
//按随机的堆优先级进行合并
if(T[x].pri<T[y].pri){//情况3：这里代码实现小根堆，x的随机权值小于y的，所以这种情况y需要是x的子树
T[x].r=merge(T[x].r,y);//x的左子树不用管，右子树和y合并 （要求x内元素小于y内元素）
up(x);//更新x
return x;//返回合并后的根
}
else{//情况4：y的随机权值小于x的，所以x需要是y的子节点
T[y].l=merge(x,T[y].l);//y的右子树不用管，左子树和x合并 （要求x内元素小于y内元素）
up(y);//更新y
return y;//返回合并后的根
}
}
void ins(int x){//插入元素x
pair<int,int> tmp1=split(root,x-1);//将原树分裂为小于x的和大于等于x的
pair<int,int> tmp2=split(tmp1.second,x);//将大于等于x的数分裂成等于x的和大于x的
if(tmp2.first){//存在等于x的节点（即第二次分裂的首项）
++T[tmp2.first].cnt;//个数+1
up(tmp2.first);//更新
}
else{//不存在，需要创建
++tot;//总结点数+1
tmp2.first=tot;//设置tmp2的子节点
T[tmp2.first].cnt=1;//初始个数为1
T[tmp2.first].siz=1;//初始子树大小为1
T[tmp2.first].val=x;//值为x
T[tmp2.first].pri=rand();//权值随机
}
root=merge(tmp1.first,merge(tmp2.first,tmp2.second));//重新合并+指派新根节点
}
void del(int x){//删除元素x
pair<int,int> tmp1=split(root,x-1);//将原树分裂为小于x的和大于等于x的
pair<int,int> tmp2=split(tmp1.second,x);//将大于等于x的数分裂成等于x的和大于x的
if(tmp2.first&&T[tmp2.first].cnt>1){//等于x的节点个数>1
--T[tmp2.first].cnt;//个数-1
up(tmp2.first);//更新
root=merge(tmp1.first,merge(tmp2.first,tmp2.second));//重新合并+指派新根节点
}
else{//需要删除
root=merge(tmp1.first,tmp2.second);//把x挤掉即可
}
}
int rnk(int rt,int x){//求在rt的子树内x的排名
if(rt==0) return 1;//无效，第一名
if(x==T[rt].val) return T[T[rt].l].siz+1;//刚好等于rt：左子树里所有节点数量+1就是排名
if(x<T[rt].val) return rnk(T[rt].l,x);//在左子树内：直接在左子树里搞就可以了
return T[T[rt].l].siz+T[rt].cnt+rnk(T[rt].r,x);//在右子树内：左子树内个数+根节点个数+在右子树里的排名
}
int kth(int rt,int x){//求rt子树内的第x名
if(rt==0) return 0;//无效
if(x<=T[T[rt].l].siz) return kth(T[rt].l,x);//在左子树内：直接在左子树里搞就可以了
if(x<=T[T[rt].l].siz+T[rt].cnt) return T[rt].val;//刚好等于rt：返回rt.val
return kth(T[rt].r,x-T[T[rt].l].siz-T[rt].cnt);//在右子树内：右子树内x减去左子树和根的大小的排名
}
int pre(int rt,int x){//求x在rt子树内的前驱
if(rt==0) return -inf;//无效，返回负无穷
if(x<=T[rt].val) return pre(T[rt].l,x);//在左子树内：返回左子树内的前驱
return max(T[rt].val,pre(T[rt].r,x));//返回右子树内的前驱（防止-inf，与根值取max）
}
int nxt(int rt,int x){//求x在rt子树内的后继
if(rt==0) return inf;//无效，返回无穷
if(x>=T[rt].val) return nxt(T[rt].r,x);//在右子树内：返回右子树内的后继
return min(T[rt].val,nxt(T[rt].l,x));//返回左子树内的后继（防止inf，与根值取min）
}
int q;//询问次数
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
srand(time(0));
cin>>q;
while(q--){
int op;
cin>>op;
if(op==1){//插入
int x;
cin>>x;
ins(x);
}
if(op==2){//删除
int x;
cin>>x;
del(x);
}
if(op==3){//名次
int x;
cin>>x;
cout<<rnk(root,x)<<'\n';
}
if(op==4){//第x名
int x;
cin>>x;
cout<<kth(root,x)<<'\n';
}
if(op==5){//前驱
int x;
cin>>x;
cout<<pre(root,x)<<'\n';
}
if(op==6){//后继
int x;
cin>>x;
cout<<nxt(root,x)<<'\n';
}
}
return 0;
}