首页 > 其他分享 >Splay 学习笔记

Splay 学习笔记

时间：2023-10-23 20:22:08浏览次数：52  
标签：Node 学习 Get int Pos 笔记 Splay Now 节点

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(Num<node[now].value){ now="LSon;" }="" else{="" ret+="Node[LSon].Size;" if(num="=Node[Now].Value){" splay(now);="" return="" ret+1;="" int="" get_pre(int="" num){="" 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;
}
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<ret) next="Now;" ret="min(Node[Now].Value,Ret);" now="LSon;" }="" else="" if(node[now].value<="Num){" splay(next);="" return="" ret;="" int="" main(){="" root="0;" insert(inf);="" insert(-inf);="" n,in1,in2;="" scanf("%d",&n);="" for(int="" i="1;i<=n;i++){" scanf("%d%d",&in1,&in2);="" switch="" (in1){="" case="" 1:="" insert(in2);="" break;="" 2:="" delete(in2);="" 3:="" printf("%d\n",get_rank(in2)-1);="" 4:="" printf("%d\n",get_num(in2+1));="" 5:="" printf("%d\n",get_pre(in2));="" 6:="" printf("%d\n",get_next(in2));="" 0;="" <="" code="">

luogu P1486 [NOI2004] 郁闷的出纳员

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

标签：Node,学习,Get,int,Pos,笔记,Splay,Now,节点
From： https://www.cnblogs.com/Ehundategh/p/17783388.html

相关文章

  • 【数据结构】Splay 树
    SplaySplay树（伸展树），是平衡树的一种，而且可以维护序列，进行一些序列操作。有些序列操作功能甚至是线段树实现不了的（经典的区间翻转）。维护集合时，Splay的中序遍历单调递增，而维护序列时，Splay的中序遍历是维护的序列。Splay通过均摊（势能分析）来保证复杂度正确，单次插入，删除，查找操作......
  • 算法笔记（3）模拟退火
    原发表于个人博客=模拟退火的引入假如我们有一个函数，要求它的极大值，怎么求呢？如果这个函数满足单调性，可以用二分的方法。如果这是一个单谷（或单峰）函数，可以用三分法。那要是多峰函数怎么半呢？这时就可以用随机化算法。一种朴素的方法是：每次在当前找到的最优方案\(x\)附近寻找一......
  • 算法笔记（4）莫队算法入门
    原发表于我的博客前言本来想学完回滚莫队、树上莫队、二离莫队之后一起写一个博客，但是一直学不会/kk，只好把已会的普通莫队和带修莫队写了（以后会补上的）普通莫队莫队——优雅的暴力莫队算法的引入例题：给定一个数列和若干询问，每次询问询问一段区间内不同种类数字的个数。暴力......
  • 算法笔记（5）贪心算法
    原发表于我的博客贪心算法贪心与其说是一种算法，不如说一种思想。贪心思想，顾名思义，就是总是做出当前最好的选择，这种方式可能在全局上不是最好的结果，但是在一些题目中就可以直接用。最简单的例子就是“货比三家”，在生活中，我们买东西时都会挑性价比最优的，这就是一种贪心。贪心算......
  • diffusion扩散模型\datawhale组队学习——v3先运行一半
    今天我们一起学习如何对模型微调和引导。微调，用原模型，跑新数据，得到新输出。引导，引导生成过程，改变输出结果。 作者之前用过sd模型，不同的采样方法在不同的采样步数下有不同的效果。首先采样步数并非越高越好或越低越好，有一个最佳使用区间，其次，不同采样方法有自己不同的最佳采样......
  • 算法笔记（6）数列分块
    原发表于我的博客前言分块不能说是一种数据结构，它是一种思想，无论是数列分块，块状链表，还是数论分块，莫队算法，都应用了分块的思想。本文主要介绍狭义上的分块，即数列分块。数列分块的引入数列分块可以说是暴力，一种优美的暴力，它的基本思路是，把数列分成若干块（一般取\(\sqrtn\)），分块......
  • 算法笔记（2）FHQtreap
    原发布于我的个人博客前言FHQtreap绝对是平衡树里最好写，最实用的，他几乎能做所有splay或其它平衡树能做的事，还能可持久化！这篇文章将会介绍FHQtreap的基本操作和维护区间的操作，并附上例题。基本操作FHQtreap的基本操作只有两个，分裂和合并。有些读者可能会问，分裂和合并和平衡树......
  • 【GPU】cuda(伪)编程学习
    一、编程模型主机(host)-设备(device)模型：xxxx编程模型使开发人员能够在包含cpu和gpu的异构计算机系统上编写和执行程序；核函数：从主机启动并在gpu设备上执行的函数成为核函数，是xxxx编程模型的关键组件，在设备内从空间中运行；线程层次结构：xxxx采用Grid-Workgroup-Thread层次结构来......
  • 算法笔记（1）线段树
    原发表于个人博客。前言线段树，是数据结构皇冠上的明珠（我编的）。它用途广泛，被一代代的oier应用，改进，优化。本文介绍了线段树的基础知识和各种拓展（包括权值线段树，可持久化线段树），各种优化方式（包括zkw线段树，动态开点，离散化），希望能帮到更多的oier。在学习线段树前，默认你应该学会一下......
  • OPenMMlab学习指导文档
    一、运行环境1.1cuda环境备注：cuda环境为个人学习和日常模型训练环境1.登录环境IP地址：10.201..用户名：*******密码：******要用此用户名和密码！！建议：自己创建自己的用户名和密码2.登录conda环境执行指令condaactivateopen-mmlab查看环境piplist则看到已安装的环境......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99