浅谈平衡树（treap）
浅谈平衡树（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如果没有这个数，返回0。
如果这个数刚好找到了，就在当前节点，那么就放回左子树的大小加一。
根据二叉搜索树的性质，进行递归求解。
查询排名为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));
}
同上。
模板题：Luogu P3369
参考代码：
#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