无旋Treap——FHQ Treap

基本介绍

 我们知道，有旋$Treap$通过旋转操作来维护树的平衡。但是实际上也有不用旋转就能维护树的平衡的$Treap$。它就是$FHQTreap$。一个很牛逼的东西。

 $FHQTreap$又称无旋$Treap$，由范浩强发明。它不再使用旋转操作，改用分裂$(split)$和合并$(merge)$两个操作维护树的平衡。

前置基本知识：Treap的原理

 通俗的将：$Treap=Tree+Heap$，即这是一棵具有树的性质又具有堆的性质的东西。
 平衡树上的每个节点放两个东西：树的值$val$和节点随机的堆值$key$。我们对于$val$值，维护查找树的性质，对于$key$值，我们维护堆的性质。

 我们又知道，普通的$BST$在插入有序序列的情况下树会退化成一条链，从而导致复杂度直接从$O(\log n)$上升到$O(n)$。但是$Treap$就不会（异或说很难，下文有解释）发生这种情况。堆的随机值等价于随机打乱有序序列插入的顺序。

 例如，我们要在$Treap$中插入一个有序序列$123456$，如下图所示：

 上图中浅绿色部分就是堆的随机值，原本插入有序序列$123456$，现在等价于$425136$

FHQ Treap的基本操作

 在这一部分，我主要张贴带有注释的代码，必要的时候附上几张图片并加以文字说明。

结点信息

struct FHQ{
	int ls,rs;//左右儿子 
	int val;//树的权值 
	int key;//堆的随机值 
	int size;//subtree的大小 
}t[M];
1
2
3
4
5
6

新建结点

int newbuild(int v){//新建一个权值为v的结点 
	t[++idx].val=v;
	t[idx].key=rand();//取堆的随机值 
	t[idx].size=1
	return idx;
} 
1
2
3
4
5
6

向上更新

inline void pushup(int p){
	t[p].size=t[t[p].ls].size+t[t[p].rs].size+1; 
} //跟线段树差不多 
1
2
3

分裂(split)

 分裂的方法就是按照给定值$v$将一棵树分裂成两棵树，其中一棵树上的$val$全部小于等于$v$，另一棵树上的$val$全部大于$v$。

 如果当前节点的$val\le v$，那么当前节点的左子树和它自己都属于分裂后的左$Treap$，但是在这个点的右子树中可能还存在一部分也满足$val\le v$的，此时我们还需要递归处理右子树中满足条件的部分，把满足条件的部分作为当前节点的右子树。把$x$指向左$Treap$的根。（如下图所示）

 同理，如果当前节点的$val>v$，那么当前节点的右子树和它自己都属于分裂后的右$Treap$，但是在这个点的左子树中可能还存在一部分也满足$val>v$的，此时我们还需要递归处理左子树中满足条件的部分，把满足条件的部分作为当前节点的左子树。把$y$指向右$Treap$的根。

void split(int p,int v,int &x,int &y){//传一个引用，确定左右儿子 
	if(!p){x=y=0;return;}
	if(t[p].val<=v){
		x=p;
		split(t[p].rs,v,t[p].rs,y);//右儿子中可能还有 
	}
	else{
		y=p;
		split(t[p].ls,v,x,t[p].ls);//左儿子中可能还有 
	}
	pushup(p); 
} 
1
2
3
4
5
6
7
8
9
10
11
12

 假设此时的$v$是$3$，$p$最开始指向$6$这个节点。那么我们通过自己模拟后可以发现原树被分类为了这个。（下图右）

合并

 合并其实可以看作是分裂的逆向操作。

 合并函数的两个参数：左$Treap$的根指针$x$，右$Treap$的根指针$y$。必须满足$x$中所有结点的$val$值小于等于$y$中所有结点的$val$值。（已经在分裂的时候就已经满足）。

 因为两个$Treap$已经有序，所以在合并时只需要考虑把哪科树放在上面，把哪棵树放在下面。也就是判断将哪棵树作为子树。根据堆的性质，我们将$key$值小的放在上面。递归即可解决。

int merge(int x,int y){
	if(!x or !y)return x+y;
	if(t[x].key<t[y].key){//把x放在上面 
		t[x].rs=merge(t[x].rs,y);//x已经有左儿子了，那就作为右儿子 
		pushup(x);return x;//回溯修改标记
	}
	else{//把y放在上面 
		t[y].ls=merge(x,t[y].ls);//y已经有右儿子了，那就作为左儿子 
		pushup(y);return y;
	}
}  
1
2
3
4
5
6
7
8
9
10
11

插入

 先分裂，再新建节点，再合并。

void insert(int v){
	int x,y,z;
	split(root,v,x,y);//分裂，方便之后的合并 
	z=newbuild(v);//新建一个点 
	root=merge(merge(x,z),y);//先合并x对应子树与z节点，确保val的大小 
} //更新root
1
2
3
4
5
6

删除

 删除也可以看作是插入的逆过程。
 两次分裂，第一次对整棵树按照当前的数的大小分裂，第二次对左$Treap$按照当前数大小减去$1$进行分裂，这样我们就可以得到$3$个部分(如下图左下角与右上角)，此时我们再合并y的左右儿子，相当于是删去了要删的这个数，因为它自此没有了原本的根节点的那个数。最后再按照大小顺序合并一遍即可。（图中删去$3$）

void del(int v){
	int x,y,z;
	split(root,v,x,z);
	split(x,v-1,x,y);
	y=merge(t[p].ls,t[p].rs);
	root=merge(merge(x,y),z);
} 
1
2
3
4
5
6
7

返回第k个节点

 分三种情况，第一种情况就是$k$小于等于左子树的大小，那么直接在左子树中递归查找。第二种情况就是$k$恰好等于左子树的大小加$1$，那么当前节点就是要找的数，最后一种情况就只需要在右子树中查找，但是此时的排名要减去左子树的大小$+1$.。

int get_k(int p,int k){
	if(t[t[p].ls].size<=k)get_k(t[p].ls,k);
	if(k==t[t[p].ls].size+1){
		return p;
	}
	return get_k(t[p].rs,k-t[t[p].ls].size-1);
} 
1
2
3
4
5
6
7

求前驱与求后继

 假设我们现在有这样一棵树，我们要找$5$的前驱，很显然我们可以发现$5$的前驱是$4$，于是我们就可以按照$4$来分裂，在左$Treap$中找最后一个数即可。

 找后继也是一样的，只不过要按照$v$分裂，然后在右$Treap$中找第一个就行了。（千万别忘了合并回去）

void getpre(int v){//找前驱
	int x,y;
	split(root,v-1,x,y);
	int p=get_k(x,t[x].size);
	cout<<t[p].val<<'\n';
	root=merge(x,y); 
}

void getnxt(int v){//找后继
	int x,y;
	split(root,v,x,y);
	int p=get_k(y,1);
	cout<<t[p].val<<'\n';
	root=merge(x,y);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

按照排名找值

void getvalbyrk(int root,int k){
	int p=getrk(root,k);
	cout<<t[p].val<<'\n';
}
1
2
3
4

按照值找排名

void getrkbyval(int v){
	int x,y;
	split(root,v-1,x,y);
	cout<<t[x].size+1<<'\n';
	root=merge(x,y); 
}
1
2
3
4
5
6