@zzzc18
2017-06-20T17:28:57.000000Z
字数 3391
阅读 1312
Splay
模板:普通平衡树
洛谷3369
Splay即为伸展树,本体就是一个排序二叉树,主要通过节点的父子关系改变而进行旋转,从而使得二叉树尽量平衡;
核心部分即为splay和rotate,代码中对此有清晰的讨论
#include<cstdio>
#include<algorithm>
#define MAXN 100009
using namespace std;
int n;
class SP{
public:
struct T{
int ls,rs,fa,sz,num,val;
};
int root;int size;
T tree[MAXN];
void DEBUG(int k){
if(k==0)return;
DEBUG(tree[k].ls);
printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|sz=%d|num=%d\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa,tree[k].sz,tree[k].num);
DEBUG(tree[k].rs);
}
int max_t(int x){
int k=x;
while(x){
k=x;
x=tree[x].rs;
}
return k;
}
int min_t(int x){
int k=x;
while(x){
k=x;
x=tree[x].ls;
}
return k;
}
int Find(int k,int x){
if(k==0)return 0;
if(tree[k].val==x)
return k;
else if(tree[k].val<x)
return Find(tree[k].rs,x);
else
return Find(tree[k].ls,x);
}
void update(int x){
tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
}
void rotate_l(int x){
int flag=0;
int y=tree[x].fa,z=tree[y].fa,p=tree[x].ls;
if(tree[z].rs==y)flag=0;
else flag=1;
if(z==0)
flag=-1;
tree[x].ls=y;
tree[y].rs=p;
if(flag==0)tree[z].rs=x;
else if(flag==1) tree[z].ls=x;
else root=x;
tree[x].fa=z;
tree[y].fa=x;
tree[p].fa=y;
update(y);
update(x);
}
void rotate_r(int x){
int flag=0;
int y=tree[x].fa,z=tree[y].fa,p=tree[x].rs;
if(tree[z].rs==y)flag=0;
else flag=1;
if(z==0)
flag=-1;
tree[y].ls=p;
tree[x].rs=y;
if(flag==0)tree[z].rs=x;
else if(flag==1) tree[z].ls=x;
else root=x;
tree[x].fa=z;
tree[p].fa=y;
tree[y].fa=x;
update(y);
update(x);
}
void splay(int x,int to,int type){
int y,z;
to=tree[to].fa;
if(type==1)
x=Find(root,x);
while(tree[x].fa!=to){
y=tree[x].fa;z=tree[y].fa;
if(z==to){
if(tree[y].ls==x)rotate_r(x);
else rotate_l(x);
}
else{
if(tree[z].ls==y && tree[y].ls==x){
rotate_r(y);
rotate_r(x);
}
else if(tree[z].ls==y && tree[y].rs==x)
rotate_l(x),rotate_r(x);
else if(tree[z].rs==y && tree[y].rs==x)
rotate_l(y),rotate_l(x);
else if(tree[z].rs==y && tree[y].ls==x)
rotate_r(x),rotate_l(x);
update(z);
}
}
if(to==0)root=x;
}
void insert(int &k,int v,int father){
if(k==0){
k=++size;
tree[k].val=v;
tree[k].fa=father;
tree[k].num=tree[k].sz=1;
return;
}
tree[k].sz++;
if(tree[k].val==v)
tree[k].num++;
else if(tree[k].val<v)
insert(tree[k].rs,v,k);
else
insert(tree[k].ls,v,k);
}
void del(int x){
int p=0;
if(!Find(root,x))return;
splay(x,root,1);
x=Find(root,x);
if(tree[x].num>1){
tree[x].num--;
return;
}
if(tree[x].ls*tree[x].rs==0)root=tree[x].ls+tree[x].rs;
else{
p=max_t(tree[x].ls);
tree[p].rs=tree[x].rs;
tree[tree[x].rs].fa=p;
root=tree[x].ls;
}
tree[root].fa=0;
while(p!=0){
update(p);
p=tree[p].fa;
}
}
int n2r(int x){
splay(x,root,1);
return tree[tree[root].ls].sz+1;
}
int r2n(int x){
int now=root;
while(1){
int minused=tree[now].num+tree[tree[now].ls].sz;
if(x>tree[tree[now].ls].sz && x<=minused)
break;
if(x<=tree[tree[now].ls].sz)
now=tree[now].ls;
else{
x-=minused;
now=tree[now].rs;
}
}
splay(now,root,0);
return tree[now].val;
}
int pred(int x){
int re;
insert(root,x,0);
splay(x,root,1);
if(tree[root].ls==0)
re=0;
else
re=tree[max_t(tree[root].ls)].val;
del(x);
return re;
}
int succ(int x){
int re;
insert(root,x,0);
splay(x,root,1);
if(tree[root].rs==0)
re=0;
else
re=tree[min_t(tree[root].rs)].val;
del(x);
return re;
}
}Splay;
int main(){
freopen("splay.in","r",stdin);
freopen("splay.out","w",stdout);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1)
Splay.insert(Splay.root,x,0);
else if(opt==2)
Splay.del(x);
else if(opt==3)
printf("%d\n",Splay.n2r(x));
else if(opt==4)
printf("%d\n",Splay.r2n(x));
else if(opt==5)
printf("%d\n",Splay.pred(x));
else if(opt==6)
printf("%d\n",Splay.succ(x));
//printf("----------DEBUG------------\norderNo.%d root:%d\n",i,Splay.root),Splay.DEBUG(Splay.root);
}
return 0;
}