浅谈平衡树（treap）

什么是平衡树（平衡树长啥样）

所谓平衡树，其实就是一种优化了之后的二叉搜索树，内部结构也是左边的儿子小于根节点，右边的儿子大于根节点，但是平衡树能通过一种名为旋转的操作来尽可能得让这珂树变得“矮”一点。（在二叉搜索树上遍历的时间复杂度其实就近似地等于这棵树的深度，让其“矮”一点就是在满足二叉搜索树的性质的同时也让其深度尽可能地小，以达到优化时间的目的。）具体图片请自行脑补。

平衡树能实现什么功能

这个......我也不好说，因为说不准明天谁谁谁又用平衡树搞出什么高级的功能来呢？

但是，以下这些功能肯定是能实现的：

1.插入/删除节点： 时间复杂度为 \(O(logn)\)，等于平衡树的深度。

2.查询一个数字的排名： 时间复杂度也可以近似认为是 \(O(logn)\) 。

3.查询排名为x的数的值： 时间复杂度也是 \(O(logn)\) 。

4.查询一个数的前驱和后继： 时间复杂度依旧是 \(O(logn)\) 。

5.合并和分裂： 以后讲无旋treap的时候再说。

平衡树具体的实现原理

一柯二叉搜索树（可能还是链式结构），可以通过将一柯子树内部旋转，儿子与父亲之间的相对位置进行置换，但仍然满足二叉搜索树的性质结构，以此来维护平衡树的深度尽可能地小，使一柯空树与左右两柯子树的相对高度不超过1.

旋转的依据是一柯子树的data（data是节点与节点之间的旋转依据，由随机数随机分配，松弛下来可以视做维护了平衡树的性质，具体证明请自行检索。），我们一般维护父节点的data大于（或小于）左右儿子。

具体实现

注：以下内容皆以《Lougu普通平衡树》这模板题为基本。

更新

也就是把子树大小更新一下。

void pushup(int i){//更新 
	size[i]=size[son[i][0]]+size[son[i][1]]+cnt[i];
} 

旋转

考虑一柯子树，如果其儿子节点的data大于父节点的data,那么就旋转。比如下面这张图：

（借用自zhengx辉巨佬的博客。）

上面那张图所展示的是左旋，就是将B节点转为A节点的父亲。首先，切断AB之间的连边，用一个temp来记录B节点的编号，然后将B节点的左儿子定为A节点的右儿子（满足二叉搜索树的性质）。接着，将A的父亲节点指向B，向上更新，然后将根节点指向B。

具体代码实现如下：

void rotate(int &id,int d){//d 代表旋转方向，0为左旋，1为右旋，id是根节点编号 
	int temp=son[id][d^1];
	son[id][d^1]=son[temp][d];
	son[temp][d]=id;
	pushup(id);
	pushup(temp);
	id=temp;
}

(一种比较玄妙且优雅的打法)

插入（动态建树）

考虑一个待加入的值x,如果在树中有这么一个节点记录的是这个值，那么就在这个点的cnt（记录出现次数）上加一，反之动态开点。

但是，我们在加点值的同时，也应当沿路观察是否有需要旋转的节点，然后顺便旋转了。

void add(int &id,int x){//val存的是一个节点的值，size是一柯子树的大小，而cnt就是这个值出现了多少次 
	if(!id){
//		id=New(x);
		id=++top;
		size[id]=cnt[id]=1;
		val[id]=x;//
		data[id]=rand();//初始化data值 
		return ;
	}
	if(val[id]==x){
		cnt[id]++;
		size[id]++;
		return ;
	}
	int d=x>val[id];
	
	add(son[id][d],x);
	
	if(data[son[id][d]]>data[id]) {
		rotate(id,d^1);
	}
	
	pushup(id);
//	printf("%d\n",id);
}

删除节点（删除一个值）

我们要分情况讨论：

1.如果没有这个点： 那就不理他，直接返回。

2.如果有这个点，且这个值出现的次数不为1： \(cnt--\) 便是了。

3.如果有这个点，但是这个值出现的次数只有一次： 这意味着我们要开始处理点与点之间的关系。接下来将会详细介绍。

如果说，这个点没有任何的儿子，那么，直接删去即可：

if(!son[id][0]&&!son[id][1]) {
			cnt[id]--,size[id]--;
			if(!cnt[id]) id=0;
		}

但是，如果这个点有左儿子，但是没有右儿子，那么，对着这个点右旋，把这个点移动到儿子的位置，然后递归删除：

else if(son[id][0]&&!son[id][1]){
			rotate(id,1);
			del(son[id][1],x); 
		} 

如果这个节点只有右儿子，那么，对着这个节点左旋，把这个点移动到儿子的位置，然后递归删除：

else if(!son[id][0]&&son[id][1]){
			rotate(id,0);
			del(son[id][0],x);
		}

如果这个节点有两个儿子，那么，我们对比一下两个儿子的data,然后决定自己是左旋还是右旋，然后递归删除。

else{
			int d=data[son[id][0]]>data[son[id][1]]?1:0;
			rotate(id,d);
			del(son[id][d],x);
		}

code:

void del(int &id,int x){
	if(!id) return;
	if(xval[id]) del(son[id][1],x);
	else{
		if(!son[id][0]&&!son[id][1]) {
			cnt[id]--,size[id]--;
			if(!cnt[id]) id=0;
		}
		else if(son[id][0]&&!son[id][1]){
			rotate(id,1);
			del(son[id][1],x); 
		} 
		else if(!son[id][0]&&son[id][1]){
			rotate(id,0);
			del(son[id][0],x);
		}
		else{
			int d=data[son[id][0]]>data[son[id][1]]?1:0;
			rotate(id,d);
			del(son[id][d],x);
		}
	}
	pushup(id);//别忘了更新 
}

查询一个值的排名

直接对着搜索树遍历就得了，哪管那么多有的没的。

int getRank(int id,int x){
	if(id==0) return 0;
	if(x==val[id]) return size[son[id][0]]+1;
	if(x

int getVal(int id,int rank){
	if(rank<=size[son[id][0]]) return getVal(son[id][0],rank);
	if(rank<=size[son[id][0]]+cnt[id]) return val[id];
	return getVal(son[id][1],rank-size[son[id][0]]-cnt[id]);
}

int getPre(int id,int x){
	if(!id)	 return -INF;
	if(x<=val[id]) return getPre(son[id][0],x);
	return max(val[id],getPre(son[id][1],x));
}

int getNext(int id,int x){
	if(!id) return INF;
	if(val[id]<=x) return getNext(son[id][1],x);
	return min(val[id],getNext(son[id][0],x));
}

#include 
#include 
#include 
#include 
#include 
#define Maxn 123458
using namespace std;
const int INF=1e9;
int n,top;
int size[Maxn];//以 i 为根的子树的大小
int cnt[Maxn];// 重复的数字的个数
int son[Maxn][2];//0 为左， 1为右 
int val[Maxn];//该节点存的值
int data[Maxn];//优先级
int New(int v){
	size[++top]=1;
	cnt[top]=1;
	val[top]=v;
	data[top]=rand();
	return top;
}
void pushup(int i){//更新 
	size[i]=size[son[i][0]]+size[son[i][1]]+cnt[i];
} 
void rotate(int &id,int d){//d 代表旋转方向，0为左旋，1为右旋，id是根节点编号 
	int temp=son[id][d^1];
	son[id][d^1]=son[temp][d];
	son[temp][d]=id;
	pushup(id);
	pushup(temp);
	id=temp;
}
void add(int &id,int x){//val存的是一个节点的值，size是一柯子树的大小，而cnt就是这个值出现了多少次 
	if(!id){
//		id=New(x);
		id=++top;
		size[id]=cnt[id]=1;
		val[id]=x;//
		data[id]=rand();//初始化data值 
		return ;
	}
	if(val[id]==x){
		cnt[id]++;
		size[id]++;
		return ;
	}
	int d=x>val[id];
	
	add(son[id][d],x);
	
	if(data[son[id][d]]>data[id]) {
		rotate(id,d^1);
	}
	
	pushup(id);
//	printf("%d\n",id);
}
void del(int &id,int x){
	if(!id) return;
	if(xval[id]) del(son[id][1],x);
	else{
		if(!son[id][0]&&!son[id][1]) {
			cnt[id]--,size[id]--;
			if(!cnt[id]) id=0;
		}
		else if(son[id][0]&&!son[id][1]){
			rotate(id,1);
			del(son[id][1],x); 
		} 
		else if(!son[id][0]&&son[id][1]){
			rotate(id,0);
			del(son[id][0],x);
		}
		else{
			int d=data[son[id][0]]>data[son[id][1]]?1:0;
			rotate(id,d);
			del(son[id][d],x);
		}
	}
	pushup(id);//别忘了更新 
}
int getRank(int id,int x){
	if(id==0) return 0;
	if(x==val[id]) return size[son[id][0]]+1;
	if(x