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$种情况。

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

  1. $X$旋转后到$Y$的位置。
  2. $Y$旋转后到$X$原来在$Y$的那个儿子的相对的儿子(如果$X$原来是$Y$的左儿子,$Y$旋转后就是$X$的右儿子)。
  3. $Y$的另一个不是$X$的儿子不变,$X$的原来$X$在$Y$的方向的儿子不变(如果$X$原来是$Y$的左儿子,$X$的左儿子就不变,$Y$的右儿子不变)。
  4. $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$极有可能会被卡。
图我就不画了(懒
总结在这:

  1. $X$和$Y$分别是$Y$和$Z$的同一个儿子(如$X$是$Y$的左儿子,$Y$是$Z$的左儿子),先旋转$Y$,再旋转$X$。
  2. $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();
    }
} 

评论

  1. vibrant72
    Windows Chrome 78.0.3904.108
    12月前
    2020-8-13 14:58:28

    orz

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇