30
2019
08

如何理解splay树

本文参考资料:https://www.cnblogs.com/cjyyb/p/7499020.html



学习splay树首先要学习SBT,即二叉搜索树,

二叉搜索树,对于任意一个节点,左儿子的值比它小,右儿子的值比它大
并且任意一棵子树单独拎出来也是一棵二叉搜索树
这里写图片描述

二叉搜索树进行中序遍历后序列正好是有序的,查找复杂度o(lgn)。但是如果一开始给定的序列就是有序的,我们构造的SBT会是一条长链,查找复杂度就变会o(n)了。

这里写图片描述

各位大佬们为了解决平衡树这个尴尬的问题,想出了各种方法。。
也就是弄出了各种树,AVL树,替罪羊树等等等等。。。
然后有一个注明的大佬叫做Tarjan,弄出了splay这个玩意。。。


我们考虑对一棵不平衡的树,对一些节点进行旋转,使得这棵树重新变成平衡的,并且仍然保证中序遍历是有序的。


这里写图片描述

这是一个丑陋的平衡树的一部分
其中XYZ三个是节点,ABC三个是三棵子树
现在这个玩意,我如果想把X弄到Y那个地方去要怎么办,这样的话我就经过了旋转,重构了这棵树的结构,就可能让他变得更加平衡

恩,我们来看看怎么办。。。
X是Y的左儿子,所以X < Y
Y是Z的左儿子,所以Y < Z
所以X < Z,所以如果要把X弄到Y的上面去的话,X就应该放到Y的那个位置

继续看,现在Y > X那么Y一定是X的右儿子
但是X已经有了右儿子B,
根据平衡树我们可以知道X < B < Y
所以我们可以把X的右儿子B丢给Y当做左儿子
而X的左儿子A有A < X < Y < Z显然还是X的左儿子

综上,我们一顿乱搞,原来的平衡树被我们搞成了这个样子
这里写图片描述

在检查一下
原来的大小关系是
A < X < B < Y < C < Z

把X旋转一下之后大小关系
A < X < B < Y < C < Z
诶,大小关系也没有变
所以之前那棵平衡树就可以通过旋转变成这个样子
并且这个时候还是一棵平衡树
好神奇诶。。。

但是,XYZ的关系显然不仅仅只有这一种
有Y是Z的左儿子 X是Y的左儿子
有Y是Z的左儿子 X是Y的右儿子
有Y是Z的右儿子 X是Y的左儿子
有Y是Z的右儿子 X是Y的右儿子
一共4种情况,大家可以自己画画图,转一转。

如果把上面的图画完了,我们就可以正式的来玩一玩splay了

转完了上面四种情况,我们来找找规律

最明显的一点,我们把X转到了原来Y的位置
也就是说,原来Y是Z的哪个儿子,旋转之后X就是Z的哪个儿子

继续看一看
我们发现,X是Y的哪个儿子,那么旋转完之后,X的那个儿子就不会变
什么意思?
看一看我上面画的图
X是Y的左儿子,A是X的左儿子,旋转完之后,A还是X的左儿子
这个应该不难证明
如果X是Y的左儿子,A是X的左儿子
那么A < X < Y旋转完之后A还是X的左儿子
如果X是Y的右儿子,A是X的右儿子
那么A > X > Y 只是把不等式反过来了而已

再看一下,找找规律
如果原来X是Y的哪一个儿子,那么旋转完之后Y就是X的另外一个儿子
再看看图
如果原来X是Y的左儿子,旋转之后Y是X的右儿子
如果原来X是Y的右儿子,旋转之后Y是X的左儿子
这个应该也很好证明吧。。。
如果X是右儿子 X > Y,所以旋转后Y是X的左儿子
如果X是左儿子 Y > X,所以旋转后Y是X的右儿子

所以总结一下:
1.X变到原来Y的位置
2.Y变成了 X原来在Y的 相对的那个儿子
3.Y的非X的儿子不变 X的 X原来在Y的 那个儿子不变
4.X的 X原来在Y的 相对的 那个儿子 变成了 Y原来是X的那个儿子

啊,,,写出来真麻烦,用语言来写一下
其中t是树上节点的结构体,ch数组表示左右儿子,ch[0]是左儿子,ch[1]是右儿子,ff是父节点

  void rotate(int x)//X是要旋转的节点{    int y=t[x].ff;//X的父亲
    int z=t[y].ff;//X的祖父
    int k=t[y].ch[1]==x;//X是Y的哪一个儿子 0是左儿子 1是右儿子
    t[z].ch[t[z].ch[1]==y]=x;//Z的原来的Y的位置变为X
    t[x].ff=z;//X的父亲变成Z
    t[y].ch[k]=t[x].ch[k^1];//X的与X原来在Y的相对的那个儿子变成Y的儿子
    t[t[x].ch[k^1]].ff=y;//更新父节点
    t[x].ch[k^1]=y;//X的 与X原来相对位置的儿子变成 Y
    t[y].ff=x;//更新父节点
  }


上面的代码用了很多小小小技巧
比如t[y].ch[1]==x
t[y].ch[1]是y的右儿子,如果x是右儿子,那么这个式子是1,否则是0,也正好对应着左右儿子
同样的k^1,表示相对的儿子,左儿子0^1=1 右儿子1^1=0

好了,这就是一个基本的旋转操作。

继续看接下来的东西
现在考虑一个问题
如果要把一个节点旋转到根节点(比如上面的Z节点呢)
我们是不是可以做两步,先把X转到Y再把X转到Z呢?
我们来看一看
这里写图片描述

一个这样的Splay

把X旋转到Y之后

这里写图片描述

再接着把X旋转到Z之后

这里写图片描述

好了,这就是对X连着旋转两次之后的Splay,看起来似乎没有什么问题。
但是,我们现在再来看一看
这里写图片描述
原图中的Splay有一条神奇链: Z->Y->X->B
然后再来看一看旋转完之后的Splay
这里写图片描述
也有一条链X->Z->Y->B

也就是说
如果你只对X进行旋转的话,
有一条链依旧存在,
如果是这样的话,splay很可能会被卡。

好了,
显然对于XYZ的不同情况,可以自己画图考虑一下,
如果要把X旋转到Z的位置应该如何旋转

归类一下,其实还是只有两种:
第一种,X和Y分别是Y和Z的同一个儿子
第二种,X和Y分别是Y和Z不同的儿子

对于情况一,也就是类似上面给出的图的情况,就要考虑先旋转Y再旋转X
对于情况二,自己画一下图,发现就是对X旋转两次,先旋转到Y再旋转到X

这样一想,对于splay旋转6种情况中的四种就很简单的分了类
其实另外两种情况很容易考虑,就是不存在Z节点,也就是Y节点就是Splay的根了
此时无论怎么样都是对于X向上进行一次旋转

那么splay的旋转也可以很容易的简化的写出来

void splay(int x,int goal)//将x旋转为goal的儿子,如果goal是0则旋转到根{   
 while(t[x].ff!=goal)//一直旋转到x成为goal的儿子
    {        int y=t[x].ff,z=t[y].ff;//父节点祖父节点
        if(z!=goal)//如果Y不是根节点,则分为上面两类来旋转
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);            //这就是之前对于x和y是哪个儿子的讨论
        rotate(x);//无论怎么样最后的一个操作都是旋转x
    }    if(goal==0)root=x;//如果goal是0,则将根节点更新为x
 }


这样写多简单,比另外一些人写得分6种情况讨论要简单很多。

先是查找find操作
从根节点开始,左侧都比他小,右侧都比他大,
所以只需要相应的往左/右递归
如果当前位置的val已经是要查找的数
那么直接把他Splay到根节点,方便接下来的操作
类似于二分查找,
所以时间复杂度O(logn)

inline void find(int x)//查找x的位置,并将其旋转到根节点{    
   int u=root;    
    if(!u)return;//树空
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)//当存在儿子并且当前位置的值不等于x
        u=t[u].ch[x>t[u].val];//跳转到儿子,查找x的父节点
    splay(u,0);//把当前位置旋转到根节点
}

下一个Insert操作
往Splay中插入一个数
类似于Find操作,只是如果是已经存在的数,就可以直接在查找到的节点的进行计数
如果不存在,在递归的查找过程中,会找到他的父节点的位置,
然后就会发现底下没有啦。。。
所以这个时候新建一个节点就可以了

inline void insert(int x)//插入x{    
    int u=root,ff=0;//当前位置u,u的父节点ff
    while(u&&t[u].val!=x)//当u存在并且没有移动到当前的值
    {
        ff=u;//向下u的儿子,父节点变为u
        u=t[u].ch[x>t[u].val];//大于当前位置则向右找,否则向左找
    }    if(u)//存在这个值的位置
        t[u].cnt++;//增加一个数
    else//不存在这个数字,要新建一个节点来存放
    {
        u=++tot;//新节点的位置
        if(ff)//如果父节点非根
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;//不存在儿子
        t[tot].ff=ff;//父节点
        t[tot].val=x;//值
        t[tot].cnt=1;//数量
        t[tot].size=1;//大小
    }
    splay(u,0);//把当前位置移到根,保证结构的平衡。注意前面因为更改了子树大小,所以这里必须Splay上去进行pushup保证size的正确。
}

继续,,,
前驱/后继操作Next
首先就要执行Find操作
把要查找的数弄到根节点
然后,以前驱为例
先确定前驱比他小,所以在左子树上
然后他的前驱是左子树中最大的值
所以一直跳右结点,直到没有为止
找后继反过来就行了

inline int Next(int x,int f)//查找x的前驱(0)或者后继(1){
    find(x);    int u=root;//根节点,此时x的父节点(存在的话)就是根节点
    if(t[u].val>x&&f)return u;//如果当前节点的值大于x并且要查找的是后继
    if(t[u].val<x&&!f)return u;//如果当前节点的值小于x并且要查找的是前驱
    u=t[u].ch[f];//查找后继的话在右儿子上找,前驱在左儿子上找
    while(t[u].ch[f^1])u=t[u].ch[f^1];//要反着跳转,否则会越来越大(越来越小)
    return u;//返回位置
}


还有操作呀/。。。
删除操作
现在就很简单啦
首先找到这个数的前驱,把他Splay到根节点
然后找到这个数后继,把他旋转到前驱的底下
比前驱大的数是后继,在右子树
比后继小的且比前驱大的有且仅有当前数
在后继的左子树上面,
因此直接把当前根节点的右儿子的左儿子删掉就可以啦

inline void Delete(int x)//删除x{    
    int last=Next(x,0);//查找x的前驱
    int next=Next(x,1);//查找x的后继
    splay(last,0);splay(next,last);    //将前驱旋转到根节点,后继旋转到根节点下面
    //很明显,此时后继是前驱的右儿子,x是后继的左儿子,并且x是叶子节点
    int del=t[next].ch[0];//后继的左儿子
    if(t[del].cnt>1)//如果超过一个
    {
        t[del].cnt--;//直接减少一个
        splay(del,0);//旋转
    }    else
        t[next].ch[0]=0;//这个节点直接丢掉(不存在了)
}
忽然发现我连第K大都没有写,随口口胡一下

从当前根节点开始,检查左子树大小
因为所有比当前位置小的数都在左侧
如果左侧的数的个数多余K,则证明第K大在左子树中
否则,向右子树找,找K-左子树大小-当前位置的数的个数
记住特判K恰好在当前位置。

inline int kth(int x)//查找排名为x的数{    
    int u=root;//当前根节点
    if(t[u].size<x)//如果当前树上没有这么多数
        return 0;//不存在
    while(1)
    {        int y=t[u].ch[0];//左儿子
        if(x>t[y].size+t[u].cnt)        //如果排名比左儿子的大小和当前节点的数量要大
        {
            x-=t[y].size+t[u].cnt;//数量减少
            u=t[u].ch[1];//那么当前排名的数一定在右儿子上找
        }        else//否则的话在当前节点或者左儿子上查找
            if(t[y].size>=x)//左儿子的节点数足够
                u=y;//在左儿子上继续找
            else//否则就是在当前根节点上
                return t[u].val;
    }
}


« 上一篇

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。