526互联

Splay 学习笔记

发布时间 2023-10-23 20:20:39作者: Ehundategh

Splay

概述

Splay也称伸展树，是二叉搜索树(BST)的一种近似平衡的类型，由Daniel Sleator 和 Robert Tarjan 于 1985 年发明。有着极其优秀的复杂度(均摊\(O(log_2n)\))。

可以实现Splay(旋转某节点到根)，Split(分裂)，Merge(合并)，Insert(插入)，Delete(删除)，Get_Rank(根据权值找排名)，Get_Num(根据排名找权值)，Get_Pre(找前驱)，Get_Next(找后继)。

在学习Splay之前，先确保你会普通二叉搜索树。

基础操作

New&Get

New即为新建一个节点，一个Splay树的节点需要包含以下元素：

1）LeftS,RightS(左右子节点)

2）Value,Count(当前点的权值以及点的个数)

3）Father(当前点的父亲节点--我们定义根节点的父亲为0号节点)

4）Size(当前节点为根的树的大小)

Get即为判断其是否为其父亲的左子节点，方便以后的操作。

以下为这两个操作的Code

int New(int Value){
    Node[++cnt]={0,0,0,Value,1,1};
    return cnt;
}

bool Get(int Now){
    return Now==Node[Fa].LeftS;
}

Update(Maintain)

Update即为更新当前点的Size，\(Size_x=Size_{LeftS}+Size_{RightS}+Count_x\)

单独提这个操作出来是因为这个操作太过于重要了，这个操作如果缺少了那么就会出现很多问题。

一定不要忘了！！！

以下为Code

void Update(int Now){
    Node[Now].Size=Node[LSon].Size+Node[RSon].Size+Node[Now].Count;
}

Zig&Zag(Rotate)

想要实现Splay这个操作，那么旋转是不可或缺的，旋转分为左旋和右旋，我们以右旋举例。

实现旋转操作，可以实现下图中的变换
Alt text
而Zig操作，我们可以看到，需要将当前节点\(x\)的父亲与\(x\)的右子节点，并且将\(x\)与其父亲的父子关系互换，并且如果\(x\)原本的父亲有父亲，那么\(x\)应该与其原本的父亲的父亲相连。

旋转完之后记得Update。

以下为两种旋转的Code(当然，两个可以合成一个写)

void Zig(int Now){
    int Grand=Node[Fa].Father;
    Node[Fa].LeftS=RSon;
    Node[RSon].Father=Fa;
    if(Grand){
        if(Get(Fa)) Node[Grand].LeftS=Now;
        else Node[Grand].RightS=Now;
    }
    else{Root=Now;}
    RSon=Fa;
    Node[Fa].Father=Now;
    if(Grand) Node[Now].Father=Grand;
    else Node[Now].Father=0;
    Update(RSon);Update(Now);
}

void Zag(int Now){
    int Grand=Node[Fa].Father;
    Node[Fa].RightS=LSon;
    Node[LSon].Father=Fa;
    if(Grand){
        if(Get(Fa)) Node[Grand].LeftS=Now;
        else Node[Grand].RightS=Now;
    }
    else{Root=Now;}
    LSon=Fa;
    Node[Fa].Father=Now;
    if(Grand) Node[Now].Father=Grand;
    else Node[Now].Father=0;
    Update(LSon);Update(Now);
}

void Rotate(int Now){
    if(Now==Root) return ;
    else{
        if(Get(Now)) Zig(Now);
        else Zag(Now);
    }
    Update(Now);
}

Splay

Splay操作即是指定一个节点\(x\)将其旋转至根节点。

为了保证树的平衡性，我们在将一个节点旋转至根节点的过程中，我们并不只执行单旋转。

我们知道每进行一次旋转，当前节点的深度就会提高1，那么在其还有祖父节点时，我们就可以进行双旋转，而在其父亲节点即为根节点时，我们就进行单旋转。

双旋转分为一字旋和之子旋：

1）一字旋：当节点\(x\)与其父亲的儿子属性相同时(儿子属性：这里指其是其父亲的什么类型的儿子)，我们就可以进行一字旋，这时先旋转其父亲节点，之后在旋转\(x\)本身。

2）之子旋：当节点\(x\)与其父亲的儿子属性不同时，我们就可以进行之子旋，这时旋转两次\(x\)本身即可。

利用了这两种操作的Splay操作，才可以保证Splay树的平均树高。

以下为Splay的Code

void Splay(int Now){
    while(Now!=Root){
        if(Fa==Root) Rotate(Now);
        else{
            if(Get(Fa)==Get(Now)) Rotate(Fa),Rotate(Now);
            else Rotate(Now),Rotate(Now);
        }
        Update(Now);
    }
    Update(Now);
}

Insert

跟普通二叉查找树一样，如果当前值小于节点值，那么向左走，如果大于，那么向右走，如果等于，那么当前节点的Count+1。走到无路可走的话，就直接在当前位置新建节点。

每次插入一个节点，就要将当前节点旋转至根节点。

以下为Insert的Code

void Insert(int Value){
    int Now=New(Value),Pos;
    if(!Root){Root=Now;return;}
    Pos=Root;
    while(true){
        if(Node[Pos].Value>Node[Now].Value){
            if(Node[Pos].LeftS)Pos=Node[Pos].LeftS;
            else{
                Node[Pos].LeftS=Now;Node[Now].Father=Pos;
                Update(Now);
                Update(Pos);
                Splay(Now);
                break;
            }
        }
        else if(Node[Pos].Value==Node[Now].Value){
            Node[Pos].Count++;
            Splay(Pos);
            break;
        }
        else{
            if(Node[Pos].RightS)Pos=Node[Pos].RightS;
            else{
                Node[Pos].RightS=Now;Node[Now].Father=Pos;
                Update(Now);
                Update(Pos);
                Splay(Now);
                break;
            }
        }
    }
}

Get_Rank

根据权值求排名也是跟普通的二叉搜索树一样。每次与当前节点的值比较来判断是向左还是向右走，如果向右走那么答案累加左子树的大小以及当前点的Count，如果权值相同或者走到了空节点，那么就返回累计的值+1。

以下为Get_Rank的Code

int Get_Rank(int Num){
    int Now=Root,Ret=0;
    while(Now){
        if(Num<Node[Now].Value){
            Now=LSon;
        }
        else{
            Ret+=Node[LSon].Size;
            if(Num==Node[Now].Value){
                Splay(Now);
                return Ret+1;
            }
            Ret+=Node[Now].Count;
            Now=RSon;
        }
    }
    return Ret+1;
}

Get_Num

这部分也和普通平衡树一样。

每次向右儿子走的时候将Rank减去左子树的Size和当前点的Count即可。如果\(Rank\le0\) 说明此时已经找到了数值，返回即可。

以下是Get_Num的代码 

int Get_Num(int Rank){
    int Now=Root;
    while(Now){
        if(LSon&&Rank<=Node[LSon].Size){
            Now=LSon;
        }
        else {
            Rank-=(Node[LSon].Size+Node[Now].Count);
            if(Rank<=0){
                Splay(Now);
                return Node[Now].Value;
            }
            Now=RSon;
        }
    }
}

Get_Pre&Get_Next

这两个操作很相似，我们以前驱举例。

求前驱则是从根节点开始，每次比较当前节点与所求值的大小，如果当前点的值小于所求值，那么尝试更新前驱的值，如果更新了前驱的值，那么就更新前驱所在的节点，并向右子树走，如果当前点的值小于所求值，就向左子树走，直到走到空节点。后继同理。

每次找到的前驱和后记都要将其旋转至根节点。

以下是Get_Pre&Get_Next的代码 

int Get_Pre(int Num){
    int Now=Root,Ret=-(1<<30),Pre=Root;
    while(Now){
        if(Node[Now].Value<Num){
            if(Node[Now].Value>Ret) Pre=Now;
            Ret=max(Node[Now].Value,Ret);
            Now=RSon;
        }
        else if(Node[Now].Value>=Num){
            Now=LSon;
        }
    }
    Splay(Pre);
    return Ret;
}

int Get_Next(int Num){
    int Now=Root,Ret=1<<30,Next=Root;
    while(Now){
        if(Node[Now].Value>Num){
            if(Node[Now].Value<Ret) Next=Now;
            Ret=min(Node[Now].Value,Ret);
            Now=LSon;
        }
        else if(Node[Now].Value<=Num){
            Now=RSon;
        }
    }
    Splay(Next);
    return Ret;
}

Delete

删除操作比较复杂。

首先我们先将要删除的权值的点旋至根节点。

分情况讨论；

1）当前点的Count>1 ，将当前点的Count-1

2）当前点没有左子节点，那么直接立右子节点为根，让后将右子节点的父亲赋为0

3）当前点没有右子节点，那么直接立左子节点为跟，让后将左子节点的父亲赋为0

4）整棵树只有一个点，直接将根改为0

5）当前点既有左子节点，又有右子节点，那么我们在左子树中找到当前点的前驱节点作为新的根节点，因为只有这样的节点，右子树才为空，然后直接将原根的右子节点与新根相连即可。

以下是Delete的代码 

void Delete(int Num){
    Get_Rank(Num);
    int Now=Root;
    if(Node[Now].Count>1){Node[Now].Count--; Update(Now);}
    else if((!LSon)&&(!RSon)) Root=0;
    else if((!LSon)&&RSon){Root=RSon; Node[RSon].Father=0;}
    else if((!RSon)&&LSon){Root=LSon; Node[LSon].Father=0;}
    else if(LSon&&RSon){
        Root=LSon;
        Node[LSon].Father=0;
        Get_Pre(Num);
        Node[RSon].Father=Root;
        Node[Root].RightS=RSon;
    }
}

例题

luogu P3369【模板】普通平衡树

直接就是Splay的模板，用来Debug正好

Code
/*
 * Author:Ehundategh
 * Update:2023/10/18
 * Title:Splay.cpp
 * You steal,I kill
 */
#include 
#include 
#include 
#define MAXN 2000010
#define LSon Node[Now].LeftS
#define RSon Node[Now].RightS
#define Fa Node[Now].Father
const int INF=1<<30;
using namespace std;
int Root,cnt=0;
struct node{
    int LeftS,RightS;
    int Father,Value,Size,Count;
}Node[MAXN];
void Clear(int Now){
    Node[Now]={0,0,0,0,0,0};
}
void Print(int Now){
    if(!Now) return;
    Print(LSon);
    printf("%d\n",Node[Now].Value);
    Print(RSon);
}
bool Get(int Now){
    return Now==Node[Fa].LeftS;
}
void Update(int Now){
    Node[Now].Size=Node[LSon].Size+Node[RSon].Size+Node[Now].Count;
}
int New(int Value){
    Node[++cnt]={0,0,0,Value,1,1};
    return cnt;
}
void Zig(int Now){
    int Grand=Node[Fa].Father;
    Node[Fa].LeftS=RSon;
    Node[RSon].Father=Fa;
    if(Grand){
        if(Get(Fa)) Node[Grand].LeftS=Now;
        else Node[Grand].RightS=Now;
    }
    else{Root=Now;}
    RSon=Fa;
    Node[Fa].Father=Now;
    if(Grand) Node[Now].Father=Grand;
    else Node[Now].Father=0;
    Update(RSon);Update(Now);
}
void Zag(int Now){
    int Grand=Node[Fa].Father;
    Node[Fa].RightS=LSon;
    Node[LSon].Father=Fa;
    if(Grand){
        if(Get(Fa)) Node[Grand].LeftS=Now;
        else Node[Grand].RightS=Now;
    }
    else{Root=Now;}
    LSon=Fa;
    Node[Fa].Father=Now;
    if(Grand) Node[Now].Father=Grand;
    else Node[Now].Father=0;
    Update(LSon);Update(Now);
}
void Rotate(int Now){
    if(Now==Root) return ;
    else{
        if(Get(Now)) Zig(Now);
        else Zag(Now);
    }
    Update(Now);
}
void Splay(int Now){
    while(Now!=Root){
        if(Fa==Root) Rotate(Now);
        else{
            if(Get(Fa)==Get(Now)) Rotate(Fa),Rotate(Now);
            else Rotate(Now),Rotate(Now);
        }
        Update(Now);
    }
    Update(Now);
}
void Insert(int Value){
    int Now=New(Value),Pos;
    if(!Root){Root=Now;return;}
    Pos=Root;
    while(true){
        if(Node[Pos].Value>Node[Now].Value){
            if(Node[Pos].LeftS)Pos=Node[Pos].LeftS;
            else{
                Node[Pos].LeftS=Now;Node[Now].Father=Pos;
                Update(Now);
                Update(Pos);
                Splay(Now);
                break;
            }
        }
        else if(Node[Pos].Value==Node[Now].Value){
            Node[Pos].Count++;
            Splay(Pos);
            break;
        }
        else{
            if(Node[Pos].RightS)Pos=Node[Pos].RightS;
            else{
                Node[Pos].RightS=Now;Node[Now].Father=Pos;
                Update(Now);
                Update(Pos);
                Splay(Now);
                break;
            }
        }
    }
}
int Get_Rank(int Num){
    int Now=Root,Ret=0;
    while(Now){
        if(NumRet) Pre=Now;
            Ret=max(Node[Now].Value,Ret);
            Now=RSon;
        }
        else if(Node[Now].Value>=Num){
            Now=LSon;
        }
    }
    Splay(Pre);
    return Ret;
}
void Delete(int Num){
    Get_Rank(Num);
    int Now=Root;
    if(Node[Now].Count>1){Node[Now].Count--; Update(Now);}
    else if((!LSon)&&(!RSon)) Root=0;
    else if((!LSon)&&RSon){Root=RSon; Node[RSon].Father=0; Clear(Now);}
    else if((!RSon)&&LSon){Root=LSon; Node[LSon].Father=0; Clear(Now);}
    else if(LSon&&RSon){
        Root=LSon;
        Node[LSon].Father=0;
        Get_Pre(Num);
        Node[RSon].Father=Root;
        Node[Root].RightS=RSon;
        Clear(Now);
    }
}
int Get_Num(int Rank){
    int Now=Root;
    while(Now){
        if(LSon&&Rank<=Node[LSon].Size){
            Now=LSon;
        }
        else {
            Rank-=(Node[LSon].Size+Node[Now].Count);
            if(Rank<=0){
                Splay(Now);
                return Node[Now].Value;
            }
            Now=RSon;
        }
    }
}
int Get_Next(int Num){
    int Now=Root,Ret=1<<30,Next=Root;
    while(Now){
        if(Node[Now].Value>Num){
            if(Node[Now].Value

luogu P1486 [NOI2004] 郁闷的出纳员

思路 
仔细分析，每次对工资的操作都是对所有人而言的，那么我们可以用一个Tag来存总体偏移量，每次更新的时候查询最小的元素，如果当前值与偏移量的和小于最小值那么就将其删除，直到找不到这样的最小的数即可。
每次对于一个加入的操作，我们只需要将其的值减去偏移量然后再加入平衡树中即可。