【数据结构】Splay详解

Splay

      • 引入
  • Splay
      • 旋转操作
      • splay操作
      • 插入操作
      • 查询x排名
      • 查询排名为x
      • 删除操作
      • 查询前驱/后继
      • 模板
      • Splay时间复杂度分析
    • 进阶操作
      • 截取区间
      • 区间加,区间赋值,区间查询,区间最值
      • 区间翻转
      • 原序列整体插入
      • 指定位置插入
      • 整体插入末尾
      • 区间最大子段和
    • 一些好题
    • 参考文献

引入

首先我们要知道一个东西叫二叉搜索树。
其定义如下:

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 n n n 个结点的二叉搜索树中,这些操作的最优时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)

如图就是一颗典型的 BST(二叉查找树)
在这里插入图片描述
可是我们发现,如果树退化成一条链,那么时间复杂度将退化为 O ( n ) O(n) O(n),这是我们不能接受的,于是平衡树孕育而生,其核心就是维护一颗相对平衡的 BST。
本文将介绍Splay,虽然它并不能保证树一直是"平衡"的,但对于Splay的一系列操作,我们可以证明其每步操作的平摊复杂度都是 O ( log ⁡ n ) O(\log n) O(logn)。所以从某种意义上说,Splay也是一种平衡的二叉查找树。

Splay

旋转操作

下面参考 OI-WIKI的介绍。
在这里插入图片描述
注意,左右旋指的是向左或右旋转。
左旋为ZAG,右旋为ZIG
以下是一次标准旋转操作:
在这里插入图片描述
我们可以知道,旋转流程如下:
在这里插入图片描述

于是我们便可以写出 ZIG和ZAG函数,参考下列代码:
在这里插入图片描述
在这里插入图片描述
不过有时候为了方便表示,我们可以把两个旋转操作合并起来。
就成了 rotate(旋转)函数,以下是参考代码:

void rotate(int x){int y=fa[x],z=fa[y],id=son_(x);ch[y][id]=ch[x][id^1];if(ch[x][id^1])fa[ch[x][id^1]]=y;ch[x][id^1]=y;fa[y]=x;fa[x]=z;if(z)ch[z][y==ch[z][1]]=x;pushup(y);pushup(x);}

其中 son_( x x x)是判断 x x x 为父节点的左儿子还是右儿子,pushup为由下往上更新。

splay操作

这个操作可以说是Splay的核心操作之一,可以理解为把某个点通过旋转操作旋转到根节点。
那么如何将一个节点旋转到根节点呢?
首先有 6 6 6 种基本情况,见下图:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
那么我们只需要不断重复执行旋转操作,即可旋转到根节点。
以下是参考代码:

void splay(int x) {for (int f = fa[x]; f = fa[x], f; rotate(x))if (fa[f]) rotate(get(x) == get(f) ? f : x);rt = x;
}

一些进阶
由于后面某些操作需要用到,所以我们对splay函数进行一些修改。
具体而言,我们引入一个参数 y y y,让splay把 x x x 旋转到 y y y 的儿子上。(当 y = 0 y=0 y=0 时将 x x x 旋转到根节点)
其实也没什么改动,见参考代码:

void splay(int x,int y){while(fa[x]!=y){if(fa[fa[x]]!=y){if(son_(fa[x])==son_(x))rotate(fa[x]);elserotate(x);}rotate(x);}if(!y)rt=x;
}

插入操作

在这里插入图片描述

解释一下:
二叉树的性质使得插入操作变得非常简易,具体而言,只要值比当前节点大,就往右子树找,小就往左子树找,一样就让计数器+1,如果找不到匹配的值就直接新建一个节点。
参考代码:

	void add(int k){if(!rt){rt=++idx;cnt[rt]++,val[rt]=k;pushup(rt);return ;}int x=rt,y=0;while(1){if(val[x]==k){cnt[x]++;pushup(x),pushup(y);splay(x,0);break;}y=x;x=ch[x][val[x]<k];if(!x){cnt[++idx]++,val[idx]=k;fa[idx]=y;ch[y][val[y]<k]=idx;pushup(idx);pushup(y);splay(idx,0);break;}}}

查询x排名

这个跟插入差不多,从根节点不断往下找,每次向右子树找时加上左子树的size+1,因为左子树和根的值一定比查询值小(BST的性质)。
具体详见代码:

	int x_rank(int k){int rk=0,x=rt;while(1){if(k<val[x])x=ch[x][0];else{rk+=sz[ch[x][0]];if(!x)return rk+1;if(k==val[x]){splay(x,0);return rk+1;}rk+=cnt[x];x=ch[x][1];}}}

查询排名为x

这个跟上面两个操作都差不多,不断往下找就行了。
看着代码,画画图也就能理解了。

	int kth(int k){int x=rt;while(1){if(ch[x][0]&&k<=sz[ch[x][0]])x=ch[x][0];else{k-=sz[ch[x][0]];if(k<=cnt[x]){splay(x,0);return val[x];}k-=cnt[x];x=ch[x][1];}}}

删除操作

在这里插入图片描述
这个就感性理解一下。
参考代码:

	void del(int k){x_rank(k);int x=rt,y=0;if(cnt[rt]>1)cnt[rt]--,pushup(rt);else if(!ch[rt][0]&&!ch[rt][1])clean(rt),rt=0;else if(!ch[rt][0]){rt=ch[rt][1];fa[rt]=0;clean(x);}else if(!ch[rt][1]){rt=ch[rt][0];fa[rt]=0;clean(x);}else{pre();fa[ch[x][1]]=rt;ch[rt][1]=ch[x][1];clean(x),pushup(rt);}}

或者还有一种方式,我们把 x x x 的前驱旋转到根节点,再把 x x x 的后继旋转到根节点的右子树上,这样根节点的右子树的左儿子即为目标节点,直接断开联系即为删除。
参考代码:

void del(int x){int l=kth(x-1),r=kth(r+1);splay(l,0),splay(r,l);fa[ch[r][0]]=0,ch[r][0]=0;pushup(r);pushup(l);
}

查询前驱/后继

这个可以先将这个节点插入,此时它在根节点,那么前驱就是它左子树中最右的点,后继就是它右子树中最左的点。
查询完我们在删除这个点即可。
参考代码:

	int pre(){int z=ch[rt][0];while(ch[z][1])z=ch[z][1];splay(z,0);return z;}int nxt(){int z=ch[rt][1];while(ch[z][0])z=ch[z][0];splay(z,0);return z;}

模板

综合上述操作,我们即可A掉洛谷模版题。
P3369 【模板】普通平衡树

题目概述:
在这里插入图片描述
参考代码:

struct Tr_splay{int fa[N],ch[N][2],sz[N],val[N],cnt[N];void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];}void clean(int x){fa[x]=sz[x]=cnt[x]=val[x]=ch[x][0]=ch[x][1]=0;}bool son_(int x){return x==ch[fa[x]][1];}void rotate(int x){int y=fa[x],z=fa[y],id=son_(x);ch[y][id]=ch[x][id^1];if(ch[x][id^1])fa[ch[x][id^1]]=y;ch[x][id^1]=y;fa[y]=x;fa[x]=z;if(z)ch[z][y==ch[z][1]]=x;pushup(y);pushup(x);}void splay(int x,int y){while(fa[x]!=y){if(fa[fa[x]]!=y){if(son_(fa[x])==son_(x))rotate(fa[x]);elserotate(x);}rotate(x);}if(!y)rt=x;}int pre(){int z=ch[rt][0];while(ch[z][1])z=ch[z][1];splay(z,0);return z;}int nxt(){int z=ch[rt][1];while(ch[z][0])z=ch[z][0];splay(z,0);return z;}void add(int k){if(!rt){rt=++idx;cnt[rt]++,val[rt]=k;pushup(rt);return ;}int x=rt,y=0;while(1){if(val[x]==k){cnt[x]++;pushup(x),pushup(y);splay(x,0);break;}y=x;x=ch[x][val[x]<k];if(!x){cnt[++idx]++,val[idx]=k;fa[idx]=y;ch[y][val[y]<k]=idx;pushup(idx);pushup(y);splay(idx,0);break;}}}int x_rank(int k){int rk=0,x=rt;while(1){if(k<val[x])x=ch[x][0];else{rk+=sz[ch[x][0]];if(!x)return rk+1;if(k==val[x]){splay(x,0);return rk+1;}rk+=cnt[x];x=ch[x][1];}}}int kth(int k){int x=rt;while(1){if(ch[x][0]&&k<=sz[ch[x][0]])x=ch[x][0];else{k-=sz[ch[x][0]];if(k<=cnt[x]){splay(x,0);return val[x];}k-=cnt[x];x=ch[x][1];}}}void del(int k){x_rank(k);int x=rt,y=0;if(cnt[rt]>1)cnt[rt]--,pushup(rt);else if(!ch[rt][0]&&!ch[rt][1])clean(rt),rt=0;else if(!ch[rt][0]){rt=ch[rt][1];fa[rt]=0;clean(x);}else if(!ch[rt][1]){rt=ch[rt][0];fa[rt]=0;clean(x);}else{pre();fa[ch[x][1]]=rt;ch[rt][1]=ch[x][1];clean(x),pushup(rt);}}
}tree;
signed main(){IOS;cin>>m;while(m--){int x,y;cin>>x>>y;if(x==1)tree.add(y);if(x==2)tree.del(y);if(x==3)tree.add(y),cout<<tree.x_rank(y)<<"\n",tree.del(y);if(x==4)cout<<tree.kth(y)<<"\n";if(x==5)tree.add(y),cout<<tree.val[tree.pre()]<<"\n",tree.del(y);if(x==6)tree.add(y),cout<<tree.val[tree.nxt()]<<"\n",tree.del(y);}return 0;
}

Splay时间复杂度分析

这个蒟蒻不会,但可以参考 OI-WIKI的证明:
证明

进阶操作

截取区间

Splay还可应用到序列操作中,具体而言,如果我们需要对区间 [ l , r ] [l,r] [l,r]进行操作,我们只需要先将 l − 1 l-1 l1 弄到根节点,再把 r + 1 r+1 r+1 弄到根节点的右儿子上,那么它的左子树就是区间 [ l , r ] [l,r] [l,r]了。
参考代码:

	int split(int l,int r){l=kth(l-1),r=kth(r+1);splay(l,0);splay(r,l);return ch[r][0];}//返回区间[l,r]对应的子树的根节点

区间加,区间赋值,区间查询,区间最值

这个类似线段树,我们相应的维护标记,并写好pushdown即可。
区间加参考:

void pushadd(int x,int k){val[x]+=k;sum[x]+=k*sz[x];add[x]+=k;
}
void modify1(int l,int r,int k){int _=split(l,r);pushadd(_,0,k);pushup(r);pushup(l);
}

区间赋值参考:

void pushcov(int x,int k){val[x]=k;sum[x]=sz[x]*k;add[x]=0;cov[x]=1;
}
void modify(int l,int r,int k){int _=split(l,r);pushcov(_,k);pushup(r);pushup(l);
}

区间查询参考:

void ask_sum(int l,int r){int _=split(l,r);cout<<sum[_]<<"\n";
}

区间翻转

这个呢我们还是搞一个懒标记然后下传,注意各个标记之间的先后顺序。
参考代码:

	void change(int x){swap(ch[x][0],ch[x][1]);lazy[x]^=1;}void reverse(int l,int r){l=kth(l),r=kth(r+2);splay(l,0);splay(r,l);change(ch[ch[l][1]][0]);}

原序列整体插入

有时候题目会直接给我们一个初始序列,一个个插入过于麻烦,于是我们可以类似线段树直接建树。
参考代码:

	int create(int k){int x=top?rb[top--]:++ID;ch[x][0]=ch[x][1]=fa[x]=rev[x]=cov[x]=0;sz[x]=1;val[x]=mx[x]=sum[x]=k;lx[x]=rx[x]=max(0ll,k);return x;}一些毒瘤题卡空间,这样回收可以节省空间。int build(int l,int r,int *a){if(l>r)return 0;if(l==r)return create(a[l]);int mid=(l+r)>>1,x=create(a[mid]);ch[x][0]=build(l,mid-1,a);ch[x][1]=build(mid+1,r,a);fa[ch[x][0]]=fa[ch[x][1]]=x;pushup(x);return x;}
rt=build(1,n,a);

指定位置插入

这个可以参考查询排名为x的操作。
能看到这里说明你已经是大佬了,看着代码画画图即可理解吧。

	void add(int pos,int k){kth(pos);pushdown(rt);fa[ch[rt][0]]=++ID,ch[ID][0]=ch[rt][0];ch[rt][0]=ID,fa[ID]=rt;sz[ID]=1;val[ID]=sum[ID]=k;pushup(ID);pushup(rt);}

整体插入末尾

这个也比较抽象,类似于建一棵新的splay,然后合并。

	void insert(int pos,int len,int *a){int _=build(1,len,a);int y=kth(pos),x=kth(pos+1);splay(y,0);splay(x,y);ch[x][0]=_,fa[_]=x;pushup(x);pushup(y);}

区间最大子段和

参考线段树,我们维护3个标记:
lx:从左起的最大子段和
mx:整个区间的最大子段和
rx:从右起的最大子段和
参考代码:(由于同时维护区间赋值和区间翻转,代码比较抽象)

	void pushup(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];lx[x]=max(lx[ch[x][0]],sum[ch[x][0]]+val[x]+lx[ch[x][1]]);rx[x]=max(rx[ch[x][1]],sum[ch[x][1]]+val[x]+rx[ch[x][0]]);mx[x]=max(max(mx[ch[x][0]],mx[ch[x][1]]),rx[ch[x][0]]+val[x]+lx[ch[x][1]]);}void pushdown(int x){if(cov[x]){if(ch[x][0])val[ch[x][0]]=val[x],cov[ch[x][0]]=1,sum[ch[x][0]]=val[x]*sz[ch[x][0]];if(ch[x][1])val[ch[x][1]]=val[x],cov[ch[x][1]]=1,sum[ch[x][1]]=val[x]*sz[ch[x][1]];if(val[x]>0){if(ch[x][0])lx[ch[x][0]]=rx[ch[x][0]]=mx[ch[x][0]]=sum[ch[x][0]];if(ch[x][1])lx[ch[x][1]]=rx[ch[x][1]]=mx[ch[x][1]]=sum[ch[x][1]];}else{if(ch[x][0])lx[ch[x][0]]=rx[ch[x][0]]=0,mx[ch[x][0]]=val[x];if(ch[x][1])lx[ch[x][1]]=rx[ch[x][1]]=0,mx[ch[x][1]]=val[x];}cov[x]=0;}if(rev[x]){if(ch[x][0])rev[ch[x][0]]^=1,swap(ch[ch[x][0]][0],ch[ch[x][0]][1]),swap(lx[ch[x][0]],rx[ch[x][0]]);if(ch[x][1])rev[ch[x][1]]^=1,swap(ch[ch[x][1]][0],ch[ch[x][1]][1]),swap(lx[ch[x][1]],rx[ch[x][1]]);rev[x]=0;}}void ask_max_sum(){cout<<mx[rt]<<"\n";}

一些好题

P2042
P4008
P6707

参考文献

  1. OI-WIKI
  2. 伸展树的基本操作和应用——杨思雨
  3. 各位大佬的博客和题解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3248559.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

学会这个技巧,电子画册制作从此不再难

​在数字化时代&#xff0c;电子画册作为一种新型的宣传和展示工具&#xff0c;已经越来越受到企业和个人的青睐。它不仅能够以生动活泼的形式展示内容&#xff0c;还能够实现高度的互动性和分享性&#xff0c;从而大大提高信息的传播效率。然而&#xff0c;制作一款精美且功能…

【机器学习】机器学习与图像分类的融合应用与性能优化新探索

文章目录 引言第一章&#xff1a;机器学习在图像分类中的应用1.1 数据预处理1.1.1 数据清洗1.1.2 数据归一化1.1.3 数据增强 1.2 模型选择1.2.1 卷积神经网络1.2.2 迁移学习1.2.3 混合模型 1.3 模型训练1.3.1 梯度下降1.3.2 随机梯度下降1.3.3 Adam优化器 1.4 模型评估与性能优…

GESP CCF C++ 七级认证真题 2024年6月

第 1 题 下列C代码的输出结果是&#xff08; &#xff09;。 #include <iostream> #include <cmath> using namespace std; int main() { cout << sin(3.1415926 / 2); return 0; } A. 0 B. 1 C.0.5 D.0.7071 第 2 题 对于如下图的二叉树&#x…

【免费】中国电子学会所有历年真题卷全部免费

今天登录到csdn 遇到一件非常气愤的事情 原本就是电子学会网站的试卷 某些博主为了赚那么点钱 真的是不要Face了 之前没有放开资源 是因为懒得整理 为了这个不要face 花了我一下午时间把所有的资源整合在一起 现在全部拿走 全部免费&#xff01;全部免费&#xff01;全…

【网络】掌握网络基础概念

文章目录 OSI七层模型TCP/IP五层&#xff08;或四层&#xff09;模型为什么要有TCP/IP协议网络传输的基本流程网络传输流程图数据包封装和分用 网络中的地址管理IP地址Mac地址比较IP地址和Mac地址 OSI七层模型 OSI即Open System Interconnection,开发系统互连。OSI七层模型是一…

ABAP 物料主数据屏幕增强记录

参考文章&#xff1a;https://zhuanlan.zhihu.com/p/692818545 先从SPRO进入——》SAP 参考IMG——》后勤_常规——》物料主数据——》配置物料主记录——》创建定制子屏幕的程序 然后会让你创建一个函数组,此处命名为ZTEST2 &#xff08;后面才发现这张图截图不对&#xf…

昇思25天学习打卡营第13天|LLM-基于MindSpore实现的GPT对话情绪识别

打卡 目录 打卡 预装环境 流程简述 部分执行结果演示 词向量加载过程 模型结构 模型训练过程 模型预测过程 代码 预装环境 pip install -i https://pypi.mirrors.ustc.edu.cn/simple mindspore2.2.14 pip install mindnlp pip install jieba pip install spacy pip …

Typescript 实现倒计时功能 useCountdown

效果图 代码块 useCountdown.ts import {onUnmounted, reactive, ref, watch} from "vue";type union days | hours | minutes | seconds | millisecondsexport type Remains Record<union, number>;/*** 创建一个倒计时** 用法*/ export const useCountDo…

Python酷库之旅-第三方库Pandas(029)

目录 一、用法精讲 74、pandas.api.interchange.from_dataframe函数 74-1、语法 74-2、参数 74-3、功能 74-4、返回值 74-5、说明 74-6、用法 74-6-1、数据准备 74-6-2、代码示例 74-6-3、结果输出 75、pandas.Series类 75-1、语法 75-2、参数 75-3、功能 75-4…

C语言函数:编程世界的魔法钥匙(2)

引言 注&#xff1a;由于这部分内容比较抽象&#xff0c;而小编我又是一个刚刚进入编程世界的计算机小白&#xff0c;所以我的介绍可能会有点让人啼笑皆非。希望大家多多包涵&#xff01;万分感谢&#xff01;待到小编我学有所成&#xff0c;一定会把这块知识点重新介绍一遍&a…

【JAVA基础】反射

编译期和运行期 首先大家应该先了解两个概念&#xff0c;编译期和运行期&#xff0c;编译期就是编译器帮你把源代码翻译成机器能识别的代码&#xff0c;比如编译器把java代码编译成jvm识别的字节码文件&#xff0c;而运行期指的是将可执行文件交给操作系统去执行&#xff0c; …

Linux介绍和文件管理

一Linux的起源 1.Unix Dennis Ritchie和Ken Thompson发明了C语言&#xff0c;而后写出了Unix的内核 2.Minix MINIX是一种基于微 内核架构的类UNIX计算机操作系统&#xff0c;由 Andrew S. Tanenbaum发明 3.Linux内核 芬兰赫尔辛基大学的研究生Linus Torvalds基于Gcc、 ba…

stack与queue的介绍与使用

stack 栈&#xff08;stack&#xff09;是一种遵循先入后出&#xff08;FILO&#xff09;逻辑的线性数据结构。其只能从容器的一端进行元素的插入与提取操作。 我们可以把他比作串串&#xff0c;我们在串肉的时候都是从底依次往上串肉&#xff0c;然后在吃的时候是从串顶依次…

springboot websocket 知识点汇总

以下是一个详细全面的 Spring Boot 使用 WebSocket 的知识点汇总 1. 配置 WebSocket 添加依赖 进入maven官网, 搜索spring-boot-starter-websocket&#xff0c;选择版本, 然后把依赖复制到pom.xml的dependencies标签中 配置 WebSocket 创建一个配置类 WebSocketConfig&…

platformIO STM32 upload-“Failed to init device.”问题解决

因为发现自己的32板子有带自动下载功能&#xff0c;platformIO也支持串口下载&#xff0c;但一直提示这个问题 问题情况 问题解决 把BOOT0接3.3V&#xff0c;BOOT1接GND&#xff0c;再点击下载(之后接回去复位也可以显示) 这是我从一个有相同问题的人从他尝试过的解决方案中…

手动添加node包给nvm管理

1.下载二进制包文件&#xff1a;https://nodejs.org/zh-cn/download/prebuilt-binaries 2.解压后&#xff0c;改名为v20.15.1。 3.放入nvm文件夹下&#xff1a; 4.运行命令即可查看&#xff1a;nvm ls 5.命令大全&#xff1a; 更新 nvm&#xff1a; nvm install-latest-npm…

STL—string类—模拟实现

STL—string类—模拟实现 熟悉了string的结构和各自接口的使用之后&#xff0c;现在就要尝试去模拟实现string类 这个string类为了避免和我们库里的string类冲突&#xff0c;因此我们需要定义一个自己的命名空间 namespace wzf {class string{public://成员函数private://成…

java之 junit单元测试案例【经典版】

一 junit单元测试 1.1 单元测试作用 单元测试要满足AIR原则&#xff0c;即 A&#xff1a; automatic 自动化&#xff1b; I: Independent 独立性&#xff1b; R&#xff1a;Repeatable 可重复&#xff1b; 2.单元测试必须使用assert来验证 1.2 案例1 常规单元测试 1.…

H6392升压恒压芯片输入2.6V4.2V5V升压9V12V18V2.5Aic 制冷市场应用

在制冷市场应用中&#xff0c;H6392升压恒压芯片由于其多种特性和优势&#xff0c;可以找到多种应用场景。虽然直接提及“制冷市场”的具体应用可能不太常见&#xff0c;但我们可以从产品特征和典型应用中推导出一些潜在的应用场景。 制冷系统电子控制器供电&#xff1a;H6392…

让旧书重焕新生:旧书回收小程序开发

在这个数字化的时代&#xff0c;书籍依然是知识的重要载体&#xff0c;承载着无数的智慧与情感。然而&#xff0c;随着时间的推移&#xff0c;许多旧书被闲置在角落&#xff0c;逐渐被遗忘。为了让这些旧书重新发挥价值&#xff0c;我们致力于开发一款创新的旧书回收小程序&…