Splay初学习

听YZ哥哥说Splay是一种很神奇的数据结构，所以学习了一下它的最基本操作。O(1)的Spaly。

伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(logn)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator和罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的。

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。

它的优势在于不需要记录用于平衡树的冗余信息。

Splay是一种自调整数据结构，它的核心是Splay操作。

Splay操作是Rotate的升级版，该函数将子节点旋转到根，来保持Splay的复杂度。

//我们这里讲的是双旋Splay，之所以称为双旋，是因为在判断父子关系之前，要旋一次，共旋两次。

Splay操作要分两种情况讨论。

①当前要Splay的点和它的父亲及其父亲的父亲(如果它有父亲的父亲的话)在同一直线上，先旋它的父亲。

②当前要Splay的点和它的父亲及其父亲的父亲(如果它有父亲的父亲的话)不在在同一直线上，旋该节点。

插入：在插入节点后，记录插入节点的位置，Splay到根。

删除：先找到要删的节点，记录下来，没有就return。删除要分几种情况讨论；

①没有左右节点，直接clear根。

　　 ②只有左节点或右节点，用左或右节点将根覆盖，clear原来的根。

　　 ③既有左节点又有右节点，将root的前驱Splay到根，然后将root的右节点（原来的root）的右节点连接到root的右节点上就好了。

其他操作跟Treap相似。

code：

#include <cstdio>

#include <cstring>

using namespace std;

int read()

{

    char c;while(c=getchar(),(c<''||c>'')&&c!='-');

    int x=,y=;c=='-'?y=-:x=c-'';

    while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x*y;

}

int N,dist;

struct Splay{

    int tr[][],v[],tot[];

    int f[],fa[],root,cnt;

    Splay(){

        memset(tr,,sizeof tr);

        memset(v,,sizeof v);

        memset(tot,,sizeof tot);

        memset(f,,sizeof f);

        cnt=root=;

    }//初始化

    void clear(int x){tr[x][]=tr[x][]=f[x]=fa[x]=tot[x]=v[x]=;}//清除节点信息

    void up(int x){f[x]=f[tr[x][]]+f[tr[x][]]+tot[x];}//更新节点信息

    int get(int x){return tr[fa[x]][]==x;}//which son of father

    void rotate(int &x)

    {

        int ol=fa[x],olol=fa[ol],to=get(x);

        tr[ol][to]=tr[x][to^];fa[tr[x][to^]]=ol;

        fa[ol]=x;tr[x][to^]=ol;

        fa[x]=olol;

        if(olol)//如果该节点的父亲的父亲存在

            tr[olol][tr[olol][]==ol]=x;

        up(ol);up(x);//这里一定要先更新ol，在更新x，想想为什么

    }

    void splay(int x)

    {

        for(int S;S=fa[x];rotate(x))//先旋x

            if(fa[S])//S不为根

                rotate((get(x)==get(S)?S:x));//判断是否三点一线

        root=x;

    }

    void insert(int &x,int val,int pos)

    {

        if(!x){//插入

            x=++cnt;

            f[x]=tot[x]=,v[x]=val,fa[x]=pos;

            dist=x;//记录节点

            return ;

        }

        if(val==v[x]){dist=x,tot[x]++;return ;}//有一样的数

        insert(tr[x][val>v[x]],val,x);

        up(x);//更新

        return ;

    }

    int QueryX(int x,int val)//查询x的排名

    {

        if(!x)return ;

        if(val==v[x])return f[tr[x][]]+;

        int to=val>v[x];

        return QueryX(tr[x][to],val)+(to?f[tr[x][]]+tot[x]:);

    }

    int QueryK(int x,int kth)//查询排名为K的数

    {

        if(!x)return ;

        if(kth<=f[tr[x][]])return QueryK(tr[x][],kth);

        if(kth>f[tr[x][]]+tot[x])return QueryK(tr[x][],kth-(f[tr[x][]]+tot[x]));

        return v[x];

    }

    void pre(int x,int val)//前驱

    {

        if(!x)return ;

        if(val<=v[x])return pre(tr[x][],val);

        else dist=x,pre(tr[x][],val);

    }

    void bac(int x,int val)//后继

    {

        if(!x)return ;

        if(v[x]<=val)bac(tr[x][],val);

        else dist=x,bac(tr[x][],val);

    }

    int find(int x,int val)//在del之前先找节点，记录，并Splay

    {

        if(!x)return ;

        if(v[x]==val){splay(x);return x;}//找到

        int to=val>v[x];

        return find(tr[x][to],val);

    }

    void del(int x)//删除

    {

        int kkk=find(root,x);

        if(!kkk)return ;//不存在

        if(tot[root]>){

            tot[root]--,up(root);

            return ;

        }

        if(!tr[root][]&&!tr[root][]){

            clear(root),root=;

            return ;

        }

        if(!(tr[root][]*tr[root][])){

            int rt=root;

            root=tr[root][]+tr[root][];

            fa[root]=,clear(rt);//细节是要先记录root，再更新root，再将原来的root clear

            return ;

        }

        int ok=root;//原来的root

        pre(root,x);//求前驱

        splay(dist);//Splay到根

        fa[tr[ok][]]=root;

        tr[root][]=tr[ok][];

        clear(ok);up(root);fa[root]=;//clear，更新，细节是要把新根的fa清零

        return ;

    }

}W;

int main()

{

    N=read();

        while(N--){

            int o=read(),x;

                switch(o){

                    case :W.insert(W.root,read(),);W.splay(dist);break;

                    case :W.del(read());break;

                    case :printf("%d\n",W.QueryX(W.root,read()));break;

                    case :printf("%d\n",W.QueryK(W.root,read()));break;

                    case :dist=,W.pre(W.root,read());printf("%d\n",W.v[dist]);break;

                    case :dist=,W.bac(W.root,read());printf("%d\n",W.v[dist]);break;

                }

        }

}

巴特西

Splay初学习

最新文章

热门文章