Splay平衡树学习笔记

yzxoi

2020-01-20 (Updated: 2022-06-25)

splay

0 前言

突然想学$Link Cut Tree$了（当然不是因为我们班里有一个叫$LCT$的人但是$LCT$有一个非常重要的前置知识，那就是$Splay$，于是就有了此篇文章。

1 Splay原理

BST

要想理解$splay$的原理，就得先理解$BST$。二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。比如这个就是一棵二叉查找树：

但是如果这棵二叉树变得丑陋点，就成了这样：

于是最坏查询情况就变成了$O(N)$这就尴尬了。

Splay

那么怎么解决如上所示的问题呢？于是就变成了各种树。其中有一位大佬叫$Tarjan$（怎么又是他发明了$Splay$ 那么$Splay$是怎么解决这个问题的呢？ $Tarjan$想出了旋转。

2 Splay详解

Rotate

如图，我们有一棵二叉树，$X,Y,Z$分别代表三个节点，$A,B,C$分别代表三个子树。

现在，我们要把这棵二叉树的$X$节点转到$Y$节点的位置。因为$X$是$Y$的左儿子，所以$X<Y$，所以旋转后$Y$必定是$X$的右儿子。因为$Y$是$Z$的左儿子，所以$Y<Z$。所以$X<Z$，所以如果把$X转到Y$，旋转后$X$必定是$Z$的左儿子。因为$X$的子树及$X$本身构成了$Y$的左儿子，所以$X$的子树及$X$本身一定$<Y$。所以$X<B<Y$，所以$B$旋转后是$Y$的左儿子。因为$C$是$Y$的右儿子，所以$C>Y$，旋转后$C$一定是$Y$的右儿子。而$X$的左儿子$A$是最小的，所以不管他，旋转后$A$还是$X$的左儿子。检查一遍：$A<X<B<Y<C<Z$没有问题。现在虽然树的形态变了，但是它还是一棵平衡树，并且好像更好看了（雾自己再画画看，总共有$4$种情况。

图画完了，我们可以总结下规律了。

$X$旋转后到$Y$的位置。
$Y$旋转后到$X$原来在$Y$的那个儿子的相对的儿子（如果$X$原来是$Y$的左儿子，$Y$旋转后就是$X$的右儿子）。
$Y$的另一个不是$X$的儿子不变，$X$的原来$X$在$Y$的方向的儿子不变（如果$X$原来是$Y$的左儿子，$X$的左儿子就不变，$Y$的右儿子不变）。
$X$的原来$X$在$Y$的方向相对的儿子旋转后变成了原来$X$在$Y$方向上的$Y$的儿子（如果$X$原来是$Y$的左儿子，$X$的右儿子就变成了$Y$的左儿子）。

inline void rotate(int x){
    re int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x;//y为x的父亲，z为y的父亲，x是y的哪个儿子 0 是左儿子，1 是右儿子
    tr[z].ch[tr[z].ch[1]==y]=x;//1.
    tr[x].fa=z;//x的父亲变为z
    tr[y].ch[k]=tr[x].ch[k^1];//4.
    tr[tr[x].ch[k^1]].fa=y;//更新父节点
    tr[x].ch[k^1]=y;//2.
    tr[y].fa=x;//更新父节点
    upd(y);upd(x);//更新每个点的数据
}

Splay

接下来考虑下一个问题：怎样把一个节点旋转到根节点呢？（比如上文的$X$旋转到$Z$）先把$X$转到$Y$，再把$Y$转到$Z$？显然这是不行的，可以自己动手画一画，在某些情况下某条链可能仍然存在，这种情况下，$Splay$极有可能会被卡。图我就不画了（懒总结在这：

$X$和$Y$分别是$Y$和$Z$的同一个儿子（如$X$是$Y$的左儿子，$Y$是$Z$的左儿子），先旋转$Y$，再旋转$X$。
$X$和$Y$分别是$Y$和$Z$的不同儿子（如$X$是$Y$的左儿子，$Y$是$Z$的右儿子），对$X$旋转$2$次。

inline void splay(int x,int rt){
    while(tr[x].fa!=rt){//直到把x转成rt的儿子
        re int y=tr[x].fa,z=tr[y].fa;//y，z分别为x的父节点、祖节点
        if(z!=rt)//如果z不是根节点，分两类旋转
        (tr[z].ch[0]==y)^(tr[y].ch[0]==x)?rotate(x):rotate(y);//分类
        rotate(x);
    }
    if(rt==0) root=x;//如果rt=0,把根节点更新为x
}

剩下的操作

剩下的操作和普通的$BST$差不多，这里就不再介绍。

3 Splay Code

Luogu P3369 【模板】普通平衡树

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;

#define re  
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);

class Splay{
//  private:
    public:
        int root,tot;
        struct Tree{
            int fa,ch[2],val,cnt,size;
        }tr[100010];
        inline void upd(int x){
            tr[x].size=tr[tr[x].ch[0]].size+tr[tr[x].ch[1]].size+tr[x].cnt;
        }
        inline void rotate(int x){
            re int y=tr[x].fa,z=tr[y].fa,k=tr[y].ch[1]==x;
            tr[z].ch[tr[z].ch[1]==y]=x;
            tr[x].fa=z;
            tr[y].ch[k]=tr[x].ch[k^1];
            tr[tr[x].ch[k^1]].fa=y;
            tr[x].ch[k^1]=y;
            tr[y].fa=x;
            upd(y);upd(x);
        }
        inline void splay(int x,int rt){
            while(tr[x].fa!=rt){
                re int y=tr[x].fa,z=tr[y].fa;
                if(z!=rt) (tr[z].ch[0]==y)^(tr[y].ch[0]==x)?rotate(x):rotate(y);
                rotate(x);
            }
            if(rt==0) root=x;
        }
        inline void find(int x){
            re int u=root;
            if(!u) return ;
            while(tr[u].ch[x>tr[u].val]&&x!=tr[u].val) u=tr[u].ch[x>tr[u].val]; 
            splay(u,0);
        }
        inline void insert(int x){
            re int u=root,ff=0;
            while(u&&tr[u].val!=x){
                ff=u;
                u=tr[u].ch[x>tr[u].val];
            }
            if(u) tr[u].cnt++;
            else{
                u=++tot;
                if(ff) tr[ff].ch[x>tr[ff].val]=u;
                tr[u].ch[0]=tr[u].ch[1]=0;
                tr[u].fa=ff;
                tr[u].val=x;
                tr[u].cnt=1;
                tr[u].size=1;
            }
            splay(u,0);
        }
        inline int pre(int x){
            find(x);
            re int u=root;
            if(tr[u].val<x) return u;
            u=tr[u].ch[0];
            while(tr[u].ch[1]) u=tr[u].ch[1];
            return u;
        }
        inline int nxt(int x){
            find(x);
            re int u=root;
            if(tr[u].val>x) return u;
            u=tr[u].ch[1];
            while(tr[u].ch[0]) u=tr[u].ch[0];
            return u;
        }
        inline void del(int x){
            re int Pre=pre(x),Nxt=nxt(x);
            splay(Pre,0);splay(Nxt,Pre);
            re int Del=tr[Nxt].ch[0];
//          cout<<"deling "<<x<<" "<<Del<<' '<<tr[Del].cnt<<endl;
            if(tr[Del].cnt>1) tr[Del].cnt--,splay(Del,0);
            else tr[Nxt].ch[0]=0;
        }
        inline int rank(int x){
            re int u=root;
            if(tr[u].size<x) return 0;
            while(1){
                re int y=tr[u].ch[0];
                if(x>tr[y].size+tr[u].cnt) x-=tr[y].size+tr[u].cnt,u=tr[u].ch[1];
                else if(tr[y].size>=x) u=y;
                else return tr[u].val;
            }
        }
        inline int Rank(int x){
            find(x);
            return tr[tr[root].ch[0]].size;
        }
        inline void PrintSplay(){
            cout<<"Now Root = "<<root<<endl;
            for(int i=1;i<=tot;i++){
                cout<<"Node id:"<<i<<" Fa:"<<tr[i].fa<<" CHL:"<<tr[i].ch[0]<<" CHR:"<<tr[i].ch[1]<<" "<<tr[i].cnt<<" "<<tr[i].val<<" sz:"<<tr[i].size<<endl;
            }
        }
}T;
int n;
signed main(){
//  freopen("input.txt","r",stdin);
    T.root=0;T.tot=0;
    T.insert(-2147483647);
    T.insert(2147483647);
    n=I.read();
    for(int op,x,i=1;i<=n;i++){
        op=I.read();x=I.read();
        if(op==1){
            T.insert(x);
        }else if(op==2){
            T.del(x); 
        }else if(op==3){
            I.write(T.Rank(x));putchar('\n');
        }else if(op==4){
            I.write(T.rank(x+1));putchar('\n');
        }else if(op==5){
            I.write(T.tr[T.pre(x)].val);putchar('\n');
        }else if(op==6){
            I.write(T.tr[T.nxt(x)].val);putchar('\n');
        }
//      cout<<"Round "<<i<<"\n";
//      T.PrintSplay();
    }
}