Splay(伸展树)

0.准备工作

在试图学习Splay之前,我们需要对一下内容加以理解:
1.神码是Dfs序
2.神码是二叉树的旋转
3.二叉树旋转之后为什么中序遍历不变(极其重要)
4.线段树区间操作是是什么原理


1.Splay 是神码

Splay是一种最优秀比较优秀的数据结构,它支持很多操作(几乎你想得到它就做得到),但是缺点就是常数较大。
Splay满足二叉搜索树的很多性质:

1.有序性:伸展树中的每一个节点的值都大于左儿子,小于右儿子
2.中序遍历不变性:伸展树无论经过怎样的旋转,中序遍历总是不变的,而且中序遍历肯定是升序遍历(或者你也可以让他降序)
3.自我调整性:简单说就是旋旋更健康:操作之后Splay()一下就可以维护树的健康度在logn左右(每次操作的复杂度),至于Splay是什么操作,待会会讲


2.如何实现一棵简单的Splay

首先,我们需要明确几个操作,以及它们的作用 。

请自行脑补这两个操作是如何进行的,然后我们再继续。

现在,我们需要将x节点向上转移,我们可以利用zig和zag操作。但是这也分多种情况。




所以以下就是将x节点旋转到根节点的操作

好的,以上就是Splay最基本的操作之一,至于为什么要有这么多旋转法则,说白了就是为了让Splay树变健康。


3.Splay的插入操作

简单的想,我们需要找到一个节点,新建它的左儿子或者右儿子。至于如何找到那个节点,我们就要用到Splay的有序性。根节点一定比左儿子大,右儿子小。


4.Splay的前驱后继

过程类似插入操作,请自行脑补


5.Splay节点的删除

我们需要将要删除的点Splay到根节点,然后删掉它。这时候会留下两颗孤独的子树,不过没关系,我们可以合并这两棵树。


综上所述,刚才的Splay可以完成插入、删除、修改、前驱、后继等操作。但是可以更多吗?


进阶Splay操作

真不清楚为什么,网上关于这类知识的介绍少之又少。我们能做的只是看着大神们的题解,一脸懵逼。出于各种考虑(其实就是因为我不会),这里就只放思路,不提供代码了。

1.Splay全局第k大

在刚才那棵简单Splay的节点中多保存一个值:子树大小。这样就可以根据子树大小来选择要查找的值在左子树还是右子树。如此方便。

2.序列在Splay中的保存

由于Splay需要满足有序性,所以我们可以很好的用它来储存一个序列。一个一维的序列经过Splay的保存,变身成为了拓扑性质完全不同的一棵树。但是这棵树又可以完美的还原原序列,并且可以更快速的完成对原序列的操作。这就是Splay称为序列之王的原因吧。
我们对Splay单调性的要求只要改为:x节点在原序列中的位置小于右儿子的位置大于左儿子的位置。我们就可以得到一棵beautiful的Splay。

3.Splay中子序列的提取

如果我们现在需要提取原序列[l,r]的区间,怎么做呢?
由于刚才我们讨论的Splay具有各种优良的性质,所以如果我们寻找区间[l,r],我们当然希望他们在一棵子树上。由于Splay的中序不变性,只要对它进行中序遍历就可以得到原序列。那么怎么做呢?
其实只需要把原序列第(l-1)位对应的节点Splay到根节点,再把节点(r+1)Splay到根节点的右儿子,那么节点(r+1)的左子树一定就是序列[l,r]。是不是很神奇又很自然。

4.Splay中序列的反转

这里就要用到线段树中常用的一中策略:懒惰标记。
如果我们要反转序列[l,r],我们就像 3.Splay的序列提取 里一样,将[l,r]变成一个子树,然后给子树的根节点打上懒惰标记,告诉它这棵树已经被反转了
然后就是标记下传,代码大概是这样的

以及Splay的序列交换,序列求和等操作,序列加减等操作,已经可以模仿以上操作写出,这里不再继续扯淡。