jvruo

【蒟蒻数据结构】伸展树Splay
我们在之前的BLOG已经多次提到了,平衡树的本质是BST(二叉查找树),而平衡树的作用是为了加速二叉查找树,但不...
扫描右侧二维码阅读全文
23
2018/07

【蒟蒻数据结构】伸展树Splay

我们在之前的BLOG已经多次提到了,平衡树的本质是BST(二叉查找树),而平衡树的作用是为了加速二叉查找树,但不添加任何内容,可以说是BST的加速版。但是Splay却恰好相反,为了得到更多的功能,splay牺牲了时间和空间,其本质目的不是为了加速二叉排序树,而是为了增加一些普通二叉排序树所不具有的功能,所以splay可以称得上是BST的ex版,所以splay从本质目的上来说已经算不上是平衡树了,所以我们给他一个名称——伸展树。

什么是SPLAY

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

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

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

正常来说伸展树可以当作普通版平衡树,加强版平衡树和加强版线段树来用,下面我们就来重点谈论一下这两种用法和具体实现方法。

普通版平衡树用法

经典例题

作为加强版的平衡树,伸展树可以完成平衡树能做到的任何操作,即可以当作普通的平衡树完成平衡树的所有操作,不信?让我们来看一看平衡树最经典而又完全的例题吧:

[Luogu P3369] 【模板】普通平衡树
题目描述
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

插入 x 数
删除 x 数(若有多个相同的数,因只删除一个)
查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数,因输出最小的排名)
查询排名为 x 的数
求 x 的前驱(前驱定义为小于 x ,且最大的数)
求 x 的后继(后继定义为大于 x ,且最小的数)

输入输出格式
输入格式:
第一行为 n ,表示操作的个数,下面 n 行每行有两个数 opt 和 x ,opt 表示操作的序号(1≤opt≤6 )

输出格式:
对于操作 3,4,5,6每行输出一个数,表示对应答案

输入输出样例
输入样例#1:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出样例#1:
106465
84185
492737
说明
时空限制:1000ms,128M

对,这就是平衡树最基本的例题了,我们之前在二叉查找树Treap的BLOG里都引用了这道例题,因为这道例题实在是太经典了,基本涵盖了平衡树的所有基本操作,所以这次我们也无法免俗地来看看如何用splay来解决这道题目。

SPLAY写法

在这里我们还是和Treap一样从头到尾一步一步教你学会写最基本的Splay!

定义结构体
int root;//根节点是谁
struct trnode
{
    int d,n,c,f,son[2];//d为值,f为父亲编号,c为控制的节点个数,n为同值节点的个数 
}tr[110000];int len;//树上有几个节点

对于每一个节点,我们要存储六个值——本身的值d,父亲是谁f,以我为根节点的子树有几个节点c,与我值相同的点有多少个n,左儿子是谁son[0],以及右儿子是谁son[1]。至于为什么我写的是son[]数组而不是l,r在后面的程序你就知道了,这会让你的程序好写很多。

更新控制节点数
int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

这个也是二叉平衡树的基本操作了,对于任意一个节点控制的子树大小,在操作过后是会发生变化的。这时,就要对点控制子树大小进行更新,这时子树大小就是左子树大小+右子树大小+我这个点存储的点的数量。

添加一个点
int add(int d,int f)//添加值为d的点,认f为父亲,f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

和二叉查找树一样,在插入一个值为x的点时,如果树上之前没有值为x的点,我们就要开创一个值为x的点。在这个模块中,我们就实现添加值为d的点,给这点初始化一下,然后认f为父亲,f认它为孩子。

rotate旋转
int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈,R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

和Treap一样,Splay的单次旋转也分为左旋和右旋,而且旋转方法完全一样,就让我我们一起来复习一下吧:

我们知道,旋转分为两种,左旋和右旋,比如我们要把x旋转向上,为了不破坏二叉查找树的性质,那么左旋和右旋是这样的:

1.png

2.png

单次旋转的程序也和Treap完全相同,在程序中,w=0时为左旋,w=1时为右旋,不理解的同学可以先去看一下Treap的旋转操作。

Splay操作
int splay(int x,int rt)//该函数是为了让x变为rt的孩子,无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲,那么什么也不用做;不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt,那么只要x向上旋转一次(相当于跳一层) 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

这个函数的目的是什么呢?就是不管x在多下面,都要把x旋转上来变成rt的孩子。具体是是怎么操作的呢?

实现我们先看一下,如果rt是x的父亲,那么什么也不用做;不然就把x往上旋转,那旋转多少步呢?我们先看一下,设x的父亲为f,ff为x的爷爷。

如果x的爷爷就是rt,那么只要x向上旋转一次(相当于跳一层)。如果ff还是rt下面的点,那么我们就先把x旋转上来到ff的位置,具体就根据f和ff的关系和x和f的关系,分为左左,右右,左右,右左四种情况 ,对应的代码就是

                  if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
            else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
            else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

具体怎么理解呢?我们一个一个来看:

对于第一种情况,也就是左左的情况,我们只要把f右旋,再把x右旋即可:

3.png

对于第二种情况,也就是右右的情况,我们只要把f左旋,再把x左旋即可:

4.png

对于第三种情况,也就是左右的情况,我们只要把x左旋,再把x右旋即可:

5.png

对于第四种情况,也就是右左的情况,我们只要把x右旋,再把x左旋即可:

6.png

是不是很简单易懂啊ovo

查找节点地址
int findip(int d)//找值为d的节点的地址,PS:如果不存在值为d的点,就找接近d的点(可能大也可能小) 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

和二叉查找树一样,在操作当中我们需要多次寻找值为d的点在哪(比如删除节点),或者接近d的值在哪(比如加入一个节点,找到后插到它的儿子位置就好了)。我们就只需要从root开始,一层层往下,由于我们知道在二叉查找树当中,每个节点的左子节点都小于它,右子节点都大于它。所以我们只要一层层判断向左儿子走,右儿子走还是不走(找到值一样的点 或者 没有对应的儿子了)就好了。

插入数值为d的点
int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

和二叉查找树一样,在插入一个值的时候,我们需要分两种情况进行讨论:

1.这棵树是空的
那么我们只要add一个点,然后root就是这点,就可以了。

2.这棵树不是空的
那么我们可以运用之前讲到的find函数,找到值为d的点在哪里。若存在值为d的点,那么直接这个点的n++就好了,代表多了一个这个值的点;若不存在值为d的点,这表示值为d的点应该出现在找到的这个点的儿子节点上,且这个儿子节点必为空,不然的话会继续findip()下去,找到的就不是这个点了。这个时候直接在找到点的对应儿子节点加上我们要添加的点就好了。

最后由于Splay的特殊策略,我们还要把新加入的节点splay到根节点。

删除数值为d的点
int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

对比二叉查找树,splay有了旋转操作,对于删除操作的处理就简单很多了。如果这个点出现多次,即tr[x].n>1,那就直接减去一个,即tr[x].n即可。现在我们来讨论一下tr[x].n=1的情况:我们首先先把待删除点找到,然后旋转到根节点,接下来分四种情况进行讨论:

1.这个点没有左右儿子:又由于这时这个点以及旋转到了根节点,它又没有左右儿子,那删除后,这颗splay就空了,直接把根设为空,树的大小设为0即可。

2.这个点只有左子树:此时的操作也很简单,由于只有左节点,直接把整颗左子树顶上来,让左儿子当根节点就好了。

3.这个点只有右子树:此时的操作和2相似,由于只有右节点,直接把整颗右子树顶上来,让右儿子当根节点就好了。

4.既有左儿子又有右儿子:这个时候由于有了旋转操作就很好写。之前我们探讨过,当x作为根节点被删除时,把它左子树的最大值放到根节点,二叉搜索树的性质不会发生变化,那我们只要在这个时候把左子树的最右点旋转到左子树的根,把这个点设置为根,由于这个点在左子树种最大,所以此时它一定没有右儿子。所以直接把删除点的右儿子拼到它的右儿子上就好了。

寻找值为d的点的排名
int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

这个操作也很简单,我们只要找到这个点的位置,设为x。把x旋转到根,根据二叉查找树的性质,左子树的所有元素都小于它,所以此时它的排名就是左子树大小加一。

寻找排名为d的点的值
int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

和二叉查找树一样,我们要查询排名为x的数,那么我们就从根节点出发,遇到每一个节点都问一下这个点包含了多少个点啊,我们记为n,这个点的左子树有多少个点啊,我们记为l,这个右子树包含了多少点啊,我们记为r。

那么如果我们的k<=l,那就不用怀疑了,我们要查找的数在左子树里,且在左子树里也是第k大,递归去找左子树就好了。

如果我们的k>l+n,那么也不用怀疑了,这个点不可能在左子树和这个点上了,一定出现在右子树,且在右子树的排名为k-tr[lc].c-tr[x].n,注意,是k-tr[lc].c-tr[x].n,不是第k!!!这时我们递归去找右子树就好了。

剩下的情况呢?不在左子树也不在右子树,那是我们现在到的这个点了呀!直接输出就可以了!

寻找一个数的前驱
int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

这个操作也很简单,首先由于我们读入的这个数不一定在我们的二叉查找树上,所以我们先用findip()先把和这个数大小相近的点找到。

然后我们进行判断,如果此时我们得到的点的值小于读入的值,那就不用怀疑,前驱就是我们得到的点的值了,反之,我们就要把找到的点旋转到根,然后去找左子树的最大值,由于findip是和读入的数最接近的点,所以此时在左子树中找到的点一定小于读入点,所以为要求的前驱。

如果这时又没有左子树,那就没有前驱了,返回0就好了。

寻找一个数的后继
int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

和找前驱类似,所以我们先用findip()先把和这个数大小相近的点找到。

然后我们进行判断,如果此时我们得到的点的值大于读入的值,那就不用怀疑,后继就是我们得到的点的值了,反之,我们就要把找到的点旋转到根,然后去找右子树的最小值,由于findip是和读入的数最接近的点,所以此时在右子树中找到的点一定大于读入点,所以为要求的前驱。

如果这时又没有右子树,那就没有后继了,返回0就好了。

主程序
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

这部分非常简单,无脑套函数就好了。

完整代码

#include<cstdio>
#include<cstring>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值,f为父亲编号,c为控制的节点个数,n为同值节点的个数 
}tr[110000];int len;

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点,认f为父亲,f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈,R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子,无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲,那么什么也不用做;不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt,那么只要x向上旋转一次(相当于跳一层) 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址,PS:如果不存在值为d的点,就找接近d的点(可能大也可能小) 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int del(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].n>1){tr[x].n--; update(x); return 0;}
         if(tr[x].son[0]==0 && tr[x].son[1]==0){root=0;len=0;}
    else if(tr[x].son[0]==0 && tr[x].son[1]!=0){root=tr[x].son[1];tr[root].f=0;}
    else if(tr[x].son[0]!=0 && tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
    else//if(tr[x].son[0]!=0 && tr[x].son[1]!=0)
    {
        int p=tr[x].son[0];
        while(tr[p].son[1]!=0)p=tr[p].son[1];
        splay(p,x);

        int r=tr[x].son[1],R=p;

        tr[R].son[1]=r;
        tr[r].f=R;

        root=R;tr[root].f=0;
        update(R);

    }
}

int findpaiming(int d)//寻找值为d的点的排名 
{
    int x=findip(d);splay(x,0);
    return(tr[tr[x].son[0]].c+1);
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int findqianqu(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d>=d && tr[x].son[0]!=0)
    {
        x=tr[x].son[0];
        while(tr[x].son[1]!=0)x=tr[x].son[1];
    }

    if(tr[x].d>=d)x=0;
    return(tr[x].d);
}

int findhouji(int d)
{
    int x=findip(d);splay(x,0);

    if(tr[x].d<=d && tr[x].son[1]!=0)
    {
        x=tr[x].son[1];
        while(tr[x].son[0]!=0)x=tr[x].son[0];
    }

    if(tr[x].d<=d)x=0;
    return(tr[x].d);
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cz,x;
        scanf("%d%d",&cz,&x);
        if(cz==1)ins(x);
        if(cz==2)del(x);
        if(cz==3)printf("%d\n",findpaiming(x));
        if(cz==4)printf("%d\n",findshuzi(x));
        if(cz==5)printf("%d\n",findqianqu(x));
        if(cz==6)printf("%d\n",findhouji(x));
    }
    return 0; 
}

加强版平衡树

既然说它是加强版平衡树,那么它肯定能做到一些普通平衡树做不到的操作,比如最经典的,维护区间翻转后整个数列的样子。

经典例题

[luogu P3391]文艺平衡树
【题意描述】
写一种数据结构,来维护一个有序数列,其中需要提供以下操作:
翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,
结果是5 2 3 4 1
【输入格式】
第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n)
m表示翻转操作次数,接下来m行每行两个数[l,r] 数据保证 1 < =l < = r < =n
(n,m < =100000)
【输出格式】
输出一行n个数字,表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5

很明显,这道题要我们维护一个支持区间翻转的序列,那么一般的平衡树就已经做不了了,但是我们的SPLAY可以呀。

首先我们考虑如何翻转一个区间?假如我们要翻转[2,3,4]首先我们要先把这个区间分离出来,我们先把2-1,也就是1旋转到根,再把4+1也就是5旋转到1的右儿子,那么5的左儿子不就是我们要求的区间了吗?如下图:

XG1.png

那分离出区间后呢?就很简单了呀只要对这颗子树的每个点的区间进行翻转就可以了呀!

那样有的同学就会问了,如果是翻转[1,n],这样就没有l-1和r+1了,怎么办?很简单,我们只要存储n+2个点,把【1,n】放到【2,n+1】即可解决。

那旋转后的序列怎么输出呢?我们发现由于此时的SPLAY基于的二叉排序树所基于的是在序列里的位置(即对于每个点,左子树的点排的都比它前,右子树的点排的都比它后),所以只要中序遍历即可了。

程序也只要在原程序上进行一点点的增添。

增添的程序

定义结构体
struct trnode
{
    int d,n,c,f,son[2];//d为值,f为父亲编号,c为控制的节点个数,n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

对比普通平衡树的用法,在这里我们多了一个需要存储的量fz,表示这个点的左右子树是否需要翻转,true为是,false则不是。和lazy-tag的思路一样,在这个点左右子树交换后,fz会下传到左右儿子节点。

对序列翻转操作
int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

正如上面所说,我们只要把l-1旋转到头,r+1旋转到l-1的右儿子,那么r+1的左儿子就是我们要的区间了,给这颗子树的根节点打上标记就好了。

左右儿子交换与标记下传
int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

翻转操作要做的事非常简单,就是把左右儿子交换,把fz标记下传,经此而已。

操作前的翻转
int findip(int d)//找值为d的节点的地址,PS:如果不存在值为d的点,就找接近d的点(可能大也可能小) 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

我们发现在基本所有涉及到点所有操作中,都会有一步操作:判断当前到的点有没有翻转标记,有,就实行上一步的翻转操作。

我们再来看看比较特殊的splay:

int splay(int x,int rt)//该函数是为了让x变为rt的孩子,无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲,那么什么也不用做;不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt,那么只要x向上旋转一次(相当于跳一层) 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

比较特殊的,在splay中,由于要考虑到当前点,当前点的父亲,当前点的爷爷三个点,所以不仅要考虑当前点的翻转操作,还有考虑到父亲节点的翻转操作,正如:

到这里,很多人会说,对于当前点的翻转很好懂,但是对于父亲节点,你都没有翻转啊,只是改了一下标记,这行得通吗?当然,我给你举一个例子:

9.png
假如我们要把蓝色节点旋转到绿色节点的位置,那么绿色节点就是父亲,由于旋转是不改变序列的顺序的,所以我们先看一下若不旋转,直接把父亲节点的子树下所有节点左右儿子互换,序列长这样:

10.png

同样的,我们从另一个角度,将操作点先向上旋转,变成这样:

11.png

再按照上面所说的,将父亲节点的fz变为false,把向上翻转的点的fz设为true,即把操作点向上翻转后,再把整颗子树的每个点的左右儿子交换后,变成这样:

12.png

我们发现两种操作的中序遍历结果一样,代表两种操作是等价的,那么具体为什么是等价感兴趣的同学可以自行证明。

查找中序遍历
int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
} 

这个就很简单了,按照正常中序遍历——左根右遍历即可,记得在看到fz=true的点时要记得交换左右子树并把标记下传。

完整代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int root;
struct trnode
{
    int d,n,c,f,son[2];//d为值,f为父亲编号,c为控制的节点个数,n为同值节点的个数 
    bool fz;//定义这个节点为根的子树是否需要翻转 
    trnode(){fz=false;}
}tr[110000];int len,llen;

int n,m,o,p,js,jl,x,y;
int a[110000];

int update(int x)//更新x控制的节点数 
{
    int lc=tr[x].son[0];
    int rc=tr[x].son[1];
    tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}

int add(int d,int f)//添加值为d的点,认f为父亲,f认它为孩子 
{
    len++;
    tr[len].d=d;tr[len].n=1;tr[len].c=1;
    tr[len].f=f; if(d<tr[f].d)tr[f].son[0]=len; else tr[f].son[1]=len;
    tr[len].son[0]=0;tr[len].son[1]=0;
}

int whfz(int x)//对x点进行左右子树翻转 
{
    tr[x].fz=false;
    int lc=tr[x].son[0],rc=tr[x].son[1];
    swap(tr[x].son[0],tr[x].son[1]);
    tr[lc].fz=1-tr[lc].fz;
    tr[rc].fz=1-tr[rc].fz;
}

int rotate(int x,int w)
{
    int f=tr[x].f,ff=tr[f].f;//在旋转之前先确定好x的父亲和爷爷
    //开始旋转建立关系
    int r,R;//r表示儿辈,R表示父辈 

    r=tr[x].son[w],R=tr[x].f;//x的儿子准备当x父亲的新儿子 
    tr[R].son[1-w]=r;
    if(r!=0)tr[r].f=R;

    r=x,R=ff;//x准备当他爷爷新孩子 
    if(tr[R].son[0]==f) tr[R].son[0]=r; else tr[R].son[1]=r;
    tr[r].f=R;

    r=f,R=x;//x的父亲当x的儿子 
    tr[R].son[w]=r; 
    tr[r].f=R; 

    update(f);
    update(x); 
}

int splay(int x,int rt)//该函数是为了让x变为rt的孩子,无论是左孩子还是右孩子 
{
    while(tr[x].f!=rt)//如果rt是x的父亲,那么什么也不用做;不然就把x往上旋转 
    {
        int f=tr[x].f,ff=tr[f].f;//准备x的父亲和爷爷 
        if(ff==rt)//如果x的爷爷就是rt,那么只要x向上旋转一次(相当于跳一层) 
        {
            if(tr[f].son[0]==x)  rotate(x,1)  ;  else  rotate(x,0)  ;
        }
            if(tr[x].fz==true)whfz(x);
            if(tr[f].fz==true){tr[f].fz=false;tr[x].fz=true;}

              if(tr[ff].son[0]==f  &&  tr[f].son[0]==x)  {rotate(f,1);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[1]==x)  {rotate(f,0);rotate(x,0);}
        else  if(tr[ff].son[0]==f  &&  tr[f].son[1]==x)  {rotate(x,0);rotate(x,1);}
        else  if(tr[ff].son[1]==f  &&  tr[f].son[0]==x)  {rotate(x,1);rotate(x,0);}

    }
    if(rt==0) root=x;
}

int findip(int d)//找值为d的节点的地址,PS:如果不存在值为d的点,就找接近d的点(可能大也可能小) 
{
    int x=root;
    while(tr[x].d!=d)
    {
        if(tr[x].fz==true)whfz(x);
        if(d<tr[x].d)
        {
            if (tr[x].son[0]==0) break;
            else x=tr[x].son[0];
        }
        else//if(d>tr[x].d) 
        {
            if (tr[x].son[1]==0) break;
            else x=tr[x].son[1];
        }
    } 
    return x;
}

int findshuzi(int k)//寻找排名为d的点的值
{
    int x=root;
    while(1) 
    {
        if(tr[x].fz==true)whfz(x);
        int lc=tr[x].son[0],rc=tr[x].son[1];
             if(k<=tr[lc].c) x=lc;
        else if(k>tr[lc].c+tr[x].n){k=k-tr[lc].c-tr[x].n;x=rc;}
        else break;
    }
    splay(x,0);
    return(tr[x].d);
} 

int fz(int x,int y)
{
    int lc=findshuzi(x-1),rc=findshuzi(y+1);
    splay(lc,0);
    splay(rc,lc);
    int p=tr[rc].son[0];
    tr[p].fz=1-tr[p].fz;
    splay(p,0);

}

int ins(int d)//插入数值为d的点 
{
    if(root==0){ add(d,0); root=len; return 0; }
    int x=findip(d);

    if(tr[x].d==d)
    {
        tr[x].n++;
        update(x);
        splay(x,0);
    }
    else
    {
        add(d,x);
        update(x);
        splay(len,0);
    }

}

int dfs(int x)
{
    if(tr[x].fz==true)whfz(x);
    if(tr[x].son[0]!=0)dfs(tr[x].son[0]);
    llen++;a[llen]=tr[x].d;
    if(tr[x].son[1]!=0)dfs(tr[x].son[1]);
    return 0;
} 

int main()
{
    len=0;root=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++)ins(i);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        x++;y++;
        fz(x,y);
    }

    llen=0;dfs(root);
    for(int i=2;i<llen;i++)printf("%d ",a[i]-1);
    return 0; 
}

加强版线段树

什么?平衡树还能当线段树来用?确实如此!我们来稍微修改一下上面这个例子:

[luogu 还没这题]粗鄙平衡树
【题意描述】
首先读入一个序列,
写一种数据结构,来维护这一个数列,其中需要提供以下操作:

  1. 翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,
    结果是5 2 3 4 1
    2.查找一个区间的最大值
    【输入格式】
    第一行为n,m n表示初始序列有n个数,
    第二行n个数,代表这个序列开始时的数
    m表示操作次数,接下来m行每行三个数[o,l,r] ,若o=1则翻转区间【l,r】,若o=2,查找区间【l,r】的最大值,数据保证 1 < =l < = r < =n
    (n,m < =100000)
    【输出格式】
    每行一个数字,代表最大值。

这道题是不是让人耳目一新,但也是很好实现的。这道题的难点在于要在上一题的基础上支持对区间最值的查询。那就很简单了,只要在每个点加入一个存储值max,表示以这个点为根的子树的最大值,在每次update的时候顺便维护一下max值就好了,应该还是很好想到的,就不给出详细的代码了。

结语

在这篇BLOG中,我们彻底了解了splay的一些基本用法,请你务必好好消化这数据结构,因为splay真的超!级!重!要!希望你喜欢这篇BLOG!

Last modification:July 25th, 2018 at 04:18 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment