@zzzc18 2017-06-20T17:28:57.000000Z 字数 3391 阅读 1203

# Splay

Splay

Splay即为伸展树，本体就是一个排序二叉树，主要通过节点的父子关系改变而进行旋转，从而使得二叉树尽量平衡；

#include<cstdio>#include<algorithm>#define MAXN 100009using 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;}

• 私有
• 公开
• 删除