首页 > 笔记 > 各种树结构之三 Splay

各种树结构之三 Splay

丧心病狂的splay

伸展树(Splay Tree)是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。

(1) 伸展树属于二叉查找树,即它具有和二叉查找树一样的性质:假设x为树中的任意一个结点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个结点,则key[y] <= key[x];如果y是x的右子树的一个结点,则key[y] >= key[x]。

(2) 除了拥有二叉查找树的性质之外,伸展树还具有的一个特点是:当某个节点被访问时,伸展树会通过旋转使该节点成为树根。这样做的好处是,下次要访问该节点时,能够迅速的访问到该节点。

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

相比于”二叉查找树“和”AVL树“,学习伸展树时需要重点关注是”伸展树的旋转算法”。

 

变量声明:f[i]表示i的父结点,ch[i][0]表示i的左儿子,ch[i][1]表示i的右儿子,key[i]表示i的值,cnt[i]表示i结点的关键字出现的次数(bst不允许有重复的节点),size[i]表示包括i的这个子树的大小;sz为整棵树的大小,root为整棵树的根。

还有几个基本操作:

【clear操作】:将当前点的各项值都清0(用于删除之后)

【getson操作】:判断当前点是它父结点的左儿子还是右儿子

【update操作】:更新当前点的size值(用于发生修改之后)

【rotate操作】

比如我们现在有一棵splay

images

我们要把D旋转到他父亲的位置

images

我们先找到三条必须断掉的边

images

然后对于D,B>D,所以B要成为D的右孩子,但是已经有G了。因为G<B,所以正好连到B的左孩子,最后把A和D连起来

images

然后就完成了

images

具体步骤

step 1:

找出D的父亲结点(B)以及父亲的父亲(A)并记录。判断D是B的左结点还是右结点,设为K。

step 2:

将D与K关系相反的儿子的父亲,记为B与K关系相同的儿子(这里即为D的右儿子的父亲记为B的左儿子);

将D与K关系相反的儿子的父亲记为B(这里即为把G的父亲记为B);

将B的父亲即为D;将D与K关系相反的儿子记为B(这里即为把D的右儿子记为B);

将D的父亲记为A,A的儿子记为D。

step 3:

update一下当前点和各个父结点的各个值

代码

【splay操作】

伸展操作只是在不停的rotate,一直到达到根。

splay的过程中需要分类讨论,如果是三点一线的话(x,x的父亲,x的祖父)需要先rotate x的父亲,否则需要先rotate x本身(否则会形成单旋使平衡树失衡)

【insert操作】

其实插入操作是比较简单的,和普通的bst基本一样。

step 1:

如果root=0,即树为空的话,新建一个节点,直接返回即可。

step 2:

按照二叉查找树的方法一直向下找,其中:

如果遇到一个结点的关键字等于当前要插入的点的话,我们就等于把这个结点加了一个cnt。因为在bst中是不可能出现两个相同的点的。并且要将当前点和它父亲结点的各项值更新一下。做一下splay。

如果已经到了最底下了,那么就可以直接插入。整个树的大小要+1,新结点的左儿子右儿子(虽然是空)父亲还有各项值要一一对应。并且最后要做一下他父亲的update(做他自己的没有必要)。做一下splay。

【findpos操作】查询x的排名

初始化:ans=0,当前点=root

和其它二叉搜索树的操作基本一样。但是区别是:

如果x比当前结点小,即应该向左子树寻找,ans不用改变。

如果x比当前结点大,即应该向右子树寻找,ans需要加上左子树的大小以及根的大小(这里的大小指的是权值)。

不要忘记了再splay一下。

【findx操作】找到排名为x的点

初始化:当前点=root

和上面的思路基本相同:

如果当前点有左子树,并且x比左子树的大小小的话,即向左子树寻找;

否则,向右子树寻找:先判断是否有右子树,然后记录右子树的大小以及当前点的大小(都为权值),用于判断是否需要继续向右子树寻找。

【求x的前驱(后继),前驱(后继)定义为小于(大于)x,且最大(最小)的数】

这类问题可以转化为将x插入,求出树上的pre(nex),再将x删除的问题。

【pre/nex操作】

这个操作十分的简单,只需要理解一点:在我们做insert操作之后做了一遍splay。这就意味着我们把x已经splay到根了。求x的前驱其实就是求x的左子树的最右边的一个结点,后继是求x的右子树的左边一个结点。

【del操作】

删除操作是最后一个稍微有点麻烦的操作。

step 1:findpos一下x。目的是:将x旋转到根。

step 2:那么现在x就是根了。如果cnt[root]>1,即不只有一个x的话,直接-1返回。

step 3:如果root并没有孩子,就说名树上只有一个x而已,直接clear返回。

images

step 4:如果root只有左儿子或者右儿子,那么直接clear root,然后把唯一的儿子当作根就可以了(f赋0,root赋为唯一的儿子)

剩下的就是它有两个儿子的情况。

images

step 5:我们找到新根,也就是x的前驱(x左子树最大的一个点),将它旋转到根。然后将原来x的右子树接到新根的右子树上(注意这个操作需要改变父子关系)。这实际上就把x删除了。不要忘了update新根。

代码

操作均来源于bzoj3224

总代吗

The end.


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×