_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

More Senior Data Structure · 特别浅地浅谈Splay

posted on 2018-04-22 20:56:29 | under 数据结构学习 |

辣么,我要介绍我自学的 $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$ )。那么我们就先从旋转开始研究吧 $qwq$ !

由于是建立在一株二叉搜索树上的,所以当时是一条链时,旋转并不会影响树的结构 $qwqqq$ 。

于是,二叉搜索树的旋转,完!


诶,骗你的啦,怎么可能完,你要知道每个节点可都是还有子节点的,如果直接旋转的话,就会出现一个节点有三个子节点的情况 $emmmmmm$ 这可不是我们想看到的,因为瞬间你的一棵 $BT$ 就毁灭了 $qwqqqq$ 。

那么其实为了满足 $BST$ 的特性,我们在上面这个图里可以看到如下内容:

根据点权来列不等式:

$Y>X,B>X,$ 如果 $Y<B,$ 那么显然B不会跑到左子树去,所以得出结论: $$Y>B$$

所以我们可以发现,对于旋转时子节点的子树,我们完全可以将这个多余的子树转移到它原来的父节点上即可。

那么这个地方我们就得出一个宝贵的规律来:

我们定义一个结点与他父亲的关系是 $x$ ,那么在旋转时,他的父亲成为了他的 $!x$ 儿子,并且那个上文中所说的“多余结点”,同时也是当前节点的 $!x$ 儿子,但在旋转之后需要成为当前节点的“前”父节点的 $x$ 儿子。

诶,其实这是找规律啦,但是也从另一个方面揭示了二叉搜索树的的某些本质 $qwqqq$

$Talk$ $is$ $\color{silver}{cheap}$ $,show$ $you$ $the$ $\color{silver}{code}$ :

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}$ :

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;  
}

诶,上图画的好像不是很浅显,因为节点数太少了 $qnq$ ,但是无论如何,本蒟蒻用机房的 $XP$ 画图做图很难受的 $QAQ$



那么接下来……那些二叉搜索树的插入删除操作我就不赘述了,因为本身二叉搜索树就可以支持找前驱后继、找排名找数,所以只需要注意以下两点:

1.每次进行有关点的操作时都要 $Splay$ 一次,因为要维护树的随机性

2.注意第一条中的“有关点”,比如当给出排名找数的时候,由于其实跟这个点没什么关系,所以不用 $Splay$ .

$Show$ $The$ $Whole$ $Code$ :

// luogu-judger-enable-o2
#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;
}