More Senior Data Structure · 特别浅地浅谈Splay
皎月半洒花
2018-04-22 20:56:29
辣么，我要介绍我自学的 Splay 了，虽然跟大佬们讲得会有些重复，但是自认为把一些玄妙的东西点出来了 qwq。
# 引言
首先，我并没觉得 Splay 有多难……代码长的原因也就最多是因为不用指针太麻烦……就好像你链表不用指针而用数组模拟，在插入删除的时候就有你好受的了 qnq,更何况树形结构更为麻烦，在树上的操作也更加花样繁多。总之，麻烦。
但是 Splay 在我眼中却更像是一种可以放诸四海而皆可用的算法,不但可以有效替代二叉搜索树、AVL 树等数据结构，也不会由于 Treap 的随机键值而靠脸拿分（其实大多数情况下，只要没有因为被大佬 % 而 rp--，Treap 也是不错的选择），并且时间复杂度也是很可观的。
那么无论怎样，在学习一种新的、我喜欢的东西之前，总是要送一句话勉励自己，并抨击那些认为这种高级数据结构没有什么学的必要的人：
## $\color{cyan}{A}$ $\color{cyan}{person}$ $\color{cyan}{who}$ $\color{cyan}{is}$ $\color{cyan}{regarded}$ $\color{cyan}{as}$ $\color{cyan}{a}$ $\color{cyan}{loser}$ $\color{cyan}{isn't}$ $\color{cyan}{those}$ $\color{cyan}{ordinarys}$ $\color{cyan}{,but}$ $\color{cyan}{the}$ $\color{cyan}{satisfieds}$
## 最怕你一生庸碌无为，却总是安慰自己平凡可贵
那么开始吧！
## 一. 旋转是个什么东西？？？
旋转这个操作呢，在之前的数据结构中，可谓见所未见，闻所未闻（瞎扯淡ing）。那么我们就先从旋转开始研究吧！
由于是建立在一株二叉搜索树上的，所以当时是一条链时，旋转并不会影响树的结构 qwqqq。
于是，二叉搜索树的旋转，完！
_________________
诶，骗你的啦，怎么可能完，你要知道每个节点可都是还有子节点的，如果直接旋转的话，就会出现一个节点有三个子节点的情况 emmmmmm 这可不是我们想看到的，因为瞬间你的一棵 $\rm BT$ 就毁灭了 qwqqqq。
那么其实为了满足 $\rm BST$ 的特性，我们可以得出一个宝贵的规律来：
我们定义一个结点与他父亲的关系是 $x$，那么在旋转时，他的父亲成为了他的 $!x$ 儿子,并且那个上文中所说的“多余结点”，同时也是当前节点的 $!x$ 儿子，但在旋转之后需要成为当前节点的“前”父节点的 $x$ 儿子。
$Talk$ $is$ $\color{silver}{cheap}$ $,show$ $you$ $the$ $\color{silver}{code}$:
```cpp
inline void update(int x){
if(x){
sub_size[x]=cnt[x];
if(sons[x][1])sub_size[x]+=sub_size[sons[x][1]];
if(sons[x][0])sub_size[x]+=sub_size[sons[x][0]];
}
return ;
}
inline bool get_which(int x){
return sons[f[x]][1]==x;
}
inline void rotate(int x){
int father=f[x],g_father=f[father];
bool which_son=get_which(x);//当前节点的关系
sons[father][which_son]=sons[x][which_son^1];
f[sons[father][which_son]]=father;
sons[x][which_son^1]=father;
f[father]=x;
f[x]=g_father;
if(g_father){
sons[g_father][get_which(father)]=x;
}
update(x);
update(father);
}
```
`son` 表示每个节点的左右儿子，`f` 表示每个节点的父亲 `sub_size[i]` 表示以 $i$ 为根的子树的大小。
诶，为什么要记录子树大小啊？
qwqqq 是为了方便执行之后的 $zz$ 操作啊。
接下来我们看 Splay 操作，其实这个操作十分地简单，不过是拼命地向上旋转至根节点而已，但在这其中还有些地方值得注意：
$\mathcal{1.}$ 如果爷爷节点、父节点与自己不共线，那么就是这样
这时实际上并不会怎样……你就不断旋转就行了$qwq$
$\mathcal{2.}$如果三个节点共线的话，那么就先要旋转父节点，因为如果先旋转子节点的话，我们就会发现原来华丽的一条链的结构被破坏，接下来的一系列操作即会导致这棵树失衡，所以应该先旋转父节点，再旋转子节点$qwq$
╮(￣▽￣")╭虽然我不是很想做效果图，但是为了你们我忍了（逃
那么接下来是当三个点共线时的两种处理方式的不同结果：
emmmm 实质上就是说，我们在链很长的时候，每次执行先旋父节点再旋当前节点的操作，一次总操作之后，这条链的深度会减半。
$Talk$ $is$ $\color{silver}{cheap}$ $,show$ $you$ $the$ $\color{silver}{code}$:
```cpp
inline void splay(int x){
for (int fa;fa=f[x];rotate(x))
if (f[fa])
rotate((get_which(x)==get_which(fa))?fa:x);
root=x;
}
```
诶，上图画的好像不是很浅显，因为节点数太少了，但是无论如何，本蒟蒻用机房的 XP 画图做图很难受的...
____________________
那么接下来……那些二叉搜索树的插入删除操作我就不赘述了，因为本身二叉搜索树就可以支持找前驱后继、找排名找数，所以只需要注意以下两点：
1.每次进行有关点的操作时都要 Splay 一次，因为要维护树的随机性，可以理解为维护复杂度。
2.注意第一条中的“有关点”，比如当给出排名找数的时候，由于其实跟这个点没什么关系，所以不用 Splay .
$\rm Show~ The~ Whole ~Code$：
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000000
int f[MAXN],cnt[MAXN],value[MAXN],sons[MAXN][2],sub_size[MAXN],whole_size,root;
inline int qread(){
int res=0,k=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')k=-1;
c=getchar();
}
while(isdigit(c)){
res=(res<<1)+(res<<3)+c-48;
c=getchar();
}
return res*k;
}
inline void S_Clear(int x){
sons[x][0]=sons[x][1]=f[x]=sub_size[x]=cnt[x]=value[x]=0;
}
inline bool get_which(int x){
return sons[f[x]][1]==x;
}
inline void update(int x){
if (x){
sub_size[x]=cnt[x];
if (sons[x][0]) sub_size[x]+=sub_size[sons[x][0]];
if (sons[x][1]) sub_size[x]+=sub_size[sons[x][1]];
}
return ;
}
inline void rotate(int x){
int father=f[x],g_father=f[father],which_son=get_which(x);
sons[father][which_son]=sons[x][which_son^1];
f[sons[father][which_son]]=father;
sons[x][which_son^1]=father;
f[father]=x;
f[x]=g_father;
if(g_father){
sons[g_father][sons[g_father][1]==father]=x;
}
update(father);
update(x);
}
inline void splay(int x){
for (int fa;fa=f[x];rotate(x))
if (f[fa])
rotate((get_which(x)==get_which(fa))?fa:x);
root=x;
}
inline void insert(int x){
if(!root){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=f[whole_size]=0;
root=whole_size;
sub_size[whole_size]=cnt[whole_size]++;
value[whole_size]=x;
return ;
}
int now=root,fa=0;
while(1){
if(x==value[now]){
cnt[now]++;
update(now);
update(fa);
splay(now);
break;
}
fa=now;
now=sons[now][value[now]<x];
if(!now){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=0;
f[whole_size]=fa;
sub_size[whole_size]=cnt[whole_size]=1;
sons[fa][value[fa]<x]=whole_size;
value[whole_size]=x;
update(fa);
splay(whole_size);
break;
}
}
}
inline int find_num(int x){
int now=root;
while(1){
if(sons[now][0]&&x<=sub_size[sons[now][0]])
now=sons[now][0];
else {
int temp=(sons[now][0]?sub_size[sons[now][0]]:0)+cnt[now];
if(x<=temp)return value[now];
x-=temp;
now=sons[now][1];
}
}
}
inline int find_rank(int x){
int now=root,ans=0;
while(1){
if (x<value[now])
now=sons[now][0];
else{
ans+=(sons[now][0]?sub_size[sons[now][0]]:0);
if (x==value[now]){
splay(now); return ans+1;
}
ans+=cnt[now];
now=sons[now][1];
}
}
}
inline int find_pre(){
int now=sons[root][0];
while(sons[now][1])now=sons[now][1];
return now;
}
inline int find_suffix(){
int now=sons[root][1];
while(sons[now][0])now=sons[now][0];
return now;
}
inline void my_delete(int x){
int hhh=find_rank(x);
if (cnt[root]>1){
cnt[root]--;
update(root);
return;
}
if (!sons[root][0]&&!sons[root][1]) {
S_Clear(root);
root=0;
return;
}
if (!sons[root][0]){
int old_root=root;
root=sons[root][1];
f[root]=0;
S_Clear(old_root);
return;
}
else if (!sons[root][1]){
int old_root=root;
root=sons[root][0];
f[root]=0;
S_Clear(old_root);
return;
}
int left_max=find_pre(),old_root=root;
splay(left_max);
sons[root][1]=sons[old_root][1];
f[sons[old_root][1]]=root;
S_Clear(old_root);
update(root);
}
int main(){
int m,num,be_dealt;
cin>>m;
for(int i=1;i<=m;i++){
num=qread();
be_dealt=qread();
switch(num)
{
case 1:insert(be_dealt);break;
case 2:my_delete(be_dealt);break;
case 3:printf("%d\n",find_rank(be_dealt));break;
case 4:printf("%d\n",find_num(be_dealt));break;
case 5:insert(be_dealt);printf("%d\n",value[find_pre()]);my_delete(be_dealt);break;
case 6:insert(be_dealt);printf("%d\n",value[find_suffix()]);my_delete(be_dealt);break;
}
}
return 0;
}
```