平衡树（Treap）的基本操作

本文主要是介绍平衡树（Treap）的基本操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

例题1：

这是一道模板题，你需要实现一个 multiset 的基本操作。具体如下：

插入一个数 x；
删除一个数 x（保证这个数一定存在）；
查询一个数 x 是否存在。

利用数组实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=3*1e5+5;
struct edge{int ls,rs,fix,num;
};
struct node{edge tree[maxn];int root,len=0;node(){root=0;} bool check(int now,int v){if(now==0)return false; if(tree[now].num==v)return true;if(tree[now].num<v)return check(tree[now].rs,v);if(tree[now].num>v)return check(tree[now].ls,v);}void turn_R(int &now){int tmp=tree[now].ls;tree[now].ls=tree[tmp].rs;tree[tmp].rs=now;now=tmp;}void turn_L(int &now){int tmp=tree[now].rs;tree[now].rs=tree[tmp].ls;tree[tmp].ls=now;now=tmp;}void insert(int &now,int v){if(now==0){tree[++len]={0,0,rand(),v};now=len;return ;}else if(tree[now].num>=v){insert(tree[now].ls,v);if(tree[tree[now].ls].fix<tree[now].fix)turn_R(now);}else if(tree[now].num<v){insert(tree[now].rs,v);if(tree[tree[now].rs].fix<tree[now].fix)turn_L(now);}}void remove(int &now,int v){if(now==0)return ;if(tree[now].num==v){if(tree[now].ls==0||tree[now].rs==0){if(tree[now].rs)now=tree[now].rs;else now=tree[now].ls;}else if(tree[tree[now].ls].fix<tree[tree[now].rs].fix){turn_R(now);remove(tree[now].rs,v);}else {turn_L(now);remove(tree[now].ls,v);}}else if(tree[now].num<v){remove(tree[now].rs,v);}else if(tree[now].num>v){remove(tree[now].ls,v);}}
}T;
int n,x,y;
int main()
{scanf("%d",&n);while(n--){scanf("%d%d",&x,&y);if(x==1)T.insert(T.root,y);if(x==2)T.remove(T.root,y);if(x==3)printf("%d\n",T.check(T.root,y));}return 0;
}

利用指针实现

#include<bits/stdc++.h>
using namespace std;
struct edge{int num,fix;edge *ls,*rs;edge(int v){num=v;fix=rand();ls=NULL;rs=NULL;}
};
struct node{edge *root=NULL;void turn_R(edge *&now){edge *tmp=now->ls;now->ls=tmp->rs;tmp->rs=now;now=tmp;}void turn_L(edge *&now){edge *tmp=now->rs;now->rs=tmp->ls;tmp->ls=now;now=tmp;}bool check(edge *now,int v){if(now==NULL)return false;if(now->num==v)return true;if(now->num<v)return check(now->rs,v);if(now->num>v)return check(now->ls,v);}void insert(edge *&now,int v){if(now==NULL){now= new edge(v);return ;}if(now->num<=v){insert(now->rs,v);if(now->rs->fix<now->fix)turn_L(now);}else if(now->num>v){insert(now->ls,v);if(now->ls->fix<now->fix)turn_R(now);}return ;}void remove(edge *&now,int v){if(now->num==v){if(now->ls==NULL||now->rs==NULL){edge *tmp=now;if(now->ls)now=now->ls;else now=now->rs;delete tmp;}else if(now->ls->fix<now->rs->fix){turn_R(now);remove(now->rs,v);}else{turn_L(now);remove(now->ls,v);}}else if(now->num<v)remove(now->rs,v);else remove(now->ls,v);return ;}
}T;
int n,x,y;
int main()
{scanf("%d",&n);while(n--){scanf("%d%d",&x,&y);if(x==1)T.insert(T.root,y);if(x==2)T.remove(T.root,y);if(x==3)printf("%d\n",T.check(T.root,y));}return 0;
}

容易出错的点：

root没有初始化
进行删除操作时用if可能会导致树满足第一个条件后进行删除，删除后又满足第二个条件，应用else if
操作时没有修改root的值

例题2：

【模板】普通平衡树 - 洛谷

Treap实现

#include<bits/stdc++.h>
using namespace std;
struct edge{int num,fix,size,weight;edge *ls,*rs;edge(int v){num=v;fix=rand();size=1;weight=1;ls=NULL;rs=NULL;}int lsize(){return ls?ls->size:0;}int rsize(){return rs?rs->size:0;}
};
struct treap{edge *root=NULL;void update(edge *now){if(now)now->size=now->lsize()+now->rsize()+now->weight;return ;}void LeftRotate(edge *&now){
//		cout<<"turn left\n";edge *tmp=now->rs;now->rs=tmp->ls;tmp->ls=now;now=tmp;update(now->ls);update(now);return ;}void RightRotate(edge *&now){
//		cout<<"turn right\n";edge *tmp=now->ls;now->ls=tmp->rs;tmp->rs=now;now=tmp;update(now->rs);update(now);return ;}void insert(edge *&now,int v){if(!now){now= new edge(v);}else if(now->num==v){now->size++;now->weight++;}else if(now->num>v){insert(now->ls,v);if(now->ls->fix<now->fix)RightRotate(now);}else {insert(now->rs,v);if(now->rs->fix<now->fix)LeftRotate(now);}update(now);return ;}void remove(edge *&now,int v){if(!now)return ;if(now->num==v){if(now->weight>1){now->weight--;now->size--;}else if(now->ls==NULL||now->rs==NULL){
//				cout<<"start\n";edge *tmp=now;if(now->ls)now=now->ls;//这里不能写成RightRotate(now)else now=now->rs;delete tmp;
//				cout<<"out\n";}else if(now->ls->fix<now->rs->fix){RightRotate(now);remove(now->rs,v);}else {LeftRotate(now);remove(now->ls,v);}}else if(now->num<v){remove(now->rs,v);}else {remove(now->ls,v);}update(now);return;}int find_x(edge *now,int v,int rank){//查询 x数的排名(排名定义为比当前数小的数的个数 +1 )if(now->num==v)return now->lsize()+rank+1;else if(now->num>v)return find_x(now->ls,v,rank);else return find_x(now->rs,v,rank+now->lsize()+now->weight);}edge *find_pos_x(edge *now,int rank){//查询排名为 x 的数if(!now)return NULL;else if(now->lsize()>=rank)return find_pos_x(now->ls,rank);else if(now->lsize()+now->weight>=rank)return now;else return find_pos_x(now->rs,rank-now->lsize()-now->weight);}edge *find_biggest(edge *now,int v,edge *last){if(!now)return last;else if(now->num<v)return find_biggest(now->rs,v,now);else return find_biggest(now->ls,v,last);}edge *find_smallest(edge *now,int v,edge *last){if(!now)return last;else if(now->num>v)return find_smallest(now->ls,v,now);else return find_smallest(now->rs,v,last);}bool find_have(edge *now,int v){if(!now)return false;else if(now->num==v)return true;else if(now->num<v)return find_have(now->rs,v);else return find_have(now->ls,v);}
}T;
int n,x,y;
int main()
{scanf("%d",&n);while(n--){scanf("%d%d",&x,&y);if(x==1)T.insert(T.root,y);if(x==2)T.remove(T.root,y);if(x==3)printf("%d\n",T.find_x(T.root,y,0));if(x==4)printf("%d\n",T.find_pos_x(T.root,y)->num);if(x==5)printf("%d\n",T.find_biggest(T.root,y,NULL)->num);if(x==6)printf("%d\n",T.find_smallest(T.root,y,NULL)->num);if(x==7)printf("%d\n",T.find_have(T.root,y));}return 0;
}

可能出错的点：