首页 > 其他分享 >[笔记]Splay树

[笔记]Splay树

时间：2024-06-20 11:44:07浏览次数：16  
标签：pre ch int siz 笔记 Splay fa rc

前置知识：树的左旋、右旋。

Splay树是一种平衡树。能够做到每个操作均摊\(O(\log N)\)。

前言

与上文AVL树不同之处在于，AVL树在任何操作结束后，都能保证每个节点的左右子树高度相差不超过\(1\)。相应地，每个操作都是严格的\(O(\log N)\)。而Splay树并没有对“平衡”的确切定义，任何结构的树都可能是Splay树（甚至可以是一条链）。相应地，单次操作的时间复杂度是无法计算的，只能知道每个操作的均摊时间复杂度为\(O(\log N)\)。

Splay树的核心思想在于“Splay操作”。对节点\(x\)进行Splay操作，即通过一系列“zig”、“zag”及其组合操作，将\(x\)挪到根节点的位置（同时对树的结构进行一些调整，使每次操作最坏复杂度更接近\(O(\log N)\)）。

增、删、查、改……几乎每一个操作完成后都要跟着一个Splay操作，把操作的节点移到根节点。注意这样不一定能像AVL树那样，保证这棵树每个节点左右子树高度相差不超过\(1\)，不过可以证明，这种修改可以让每个操作的均摊时间复杂度变为\(O(\log N)\)。

这样，Splay的优势显现了出来：越是最近操作过的节点，到根节点的距离就越近，访问就会越快。符合实际应用时可能会出现的情况（比如我们用的输入法）。

具体操作方式见下。

代码来自Splay 详细图解 & 轻量级代码实现 - 樱雪喵，十分感谢！

各种操作

准备

#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
#define ch(x,y) tr[x].ch[y]
#define fa(x) tr[x].fa
#define v(x) tr[x].v
#define siz(x) tr[x].siz
struct tree{
	int ch[2],siz,fa,v;
	void clear(){ch[0]=ch[1]=siz=fa=v=0;}
}tr[N];
int t,cnt,root;
void clear(int u){tr[u].clear();}
int newnode(int v){v(++cnt)=v,siz(cnt)=1;return cnt;}
void update(int u){siz(u)=siz(lc(u))+siz(rc(u))+1;}//更新状态
bool get(int u){return u==rc(fa(u));}//查询u是其父节点的左子结点还是右子节点

与AVL不同，Splay不需要记录树高。

旋转 & Splay操作

void rot(int x){
	int y=fa(x),z=fa(y);//保证y!=0
	bool dir=get(x),tdir=get(y);
	if(ch(x,!dir)) fa(ch(x,!dir))=y;
	ch(y,dir)=ch(x,!dir);
	ch(x,!dir)=y;
	fa(y)=x,fa(x)=z;
	if(z) ch(z,tdir)=x;
	update(y),update(x);
}

旋转操作把左旋和右旋写在了一起，其含义也较AVL有改变。rot(x)表示通过旋转将\(x\)提升一层。

接下来讲解算法的精髓——Splay操作。

Splay操作就是不断调用rot(x)，将节点\(x\)移到根节点的位置。

这里设\(x\)的父节点为\(f\)（下图中是\(p\)）。

但旋转方式根据树的结构也有所不同，一共分为\(6\)种：zig、zig-zig、zig-zag、zag、 zag-zag、zag-zig。由于后面\(3\)种与前面\(3\)种操作是对称的，所以就只说前\(3\)种了。

下面\(3\)张图片来自OI Wiki。

1 - zig/zag

zig/zag操作，只有Splay过程中的最后一次旋转才可能会使用。

条件就是\(x\)到当前根节点的距离正好是\(1\)。

这种情况下，调用一次rot(x)即可。

2 - zig-zig/zag-zag

zig-zig/zag-zag操作，是在\(x\)到根节点距离超过\(1\)，而且\(x,y\)都是左子结点/右子节点的情况下使用的。

这种情况下，需要先调用rot(p)，再调用rot(x)。

3 - zig-zag/zag-zig

zig-zag/zag-zig操作，是在\(x\)到根节点距离超过\(1\)，而且\(x,y\)中\(1\)个是左子节点，\(1\)个是右子节点的情况下使用的。

这种情况下，需要连续调用\(2\)次rot(x)。

为什么zig-zag就是两次rot(x)，而zig-zig必须先调用rot(p)再调用rot(x)呢？

（当然，你可以发现在zig-zag的情况下是做不到rot(p)再rot(x)的）

这是为了保证时间复杂度。当然我们也可以感性理解一下：

image

如你所见，这是一条链（没错，如果依次插入\(16,15,\dots ,1\)就会这样）。

现在我们想对节点\(16\)执行Splay操作，那显然每次都是zig-zig了。

出现链不要担心，我们按照正确的操作（rot(p)再rot(x)）跑一遍：

image

我们发现，树的高度的数量级直接减少了一半。如果再对节点\(15\)进行一个Splay操作，树的高度会更加接近\(\log N\)。

但如果我们按错误的操作（两次rot(x)）来跑：

image

还是。。。一条链。

代码可以写出来了。

void splay(int x){
	for(int f;(f=fa(x));rot(x))
		if(fa(f)) rot(get(f)==get(x)?f:x);
	root=x;
}

其他操作

和普通BST一样了。。。不过要注意每个操作最后都要加Splay。否则每次操作\(O(\log N)\)复杂度会假（想象一下如果你有个操作没加Splay，又正好碰到了上面那条链的样例，它又正好不断调用这个操作，那么这条链就一直得不到调整，每次时间复杂度就是\(O(n)\)了。。。）。

插入

void ins(int v){
	int u=root,f=0;
	while(u) f=u,u=ch(u,v>v(u));//>在右，<=在左
	u=newnode(v),fa(u)=f;
	if(f) ch(f,v>v(f))=u;
	splay(u);
}

删除

void del(int v){
	int u=root,f=0;
	while(v(u)!=v&&u) f=u,u=ch(u,v>v(u));//找到要修改的节点
	if(!u){splay(f);return;}//不要忘记Splay！
	splay(u);//这里Splay到根是为了更方便操作，不用特判根了
	int pre=lc(u);
	if(!pre){root=rc(u),fa(rc(u))=0,clear(u);return;}
	while(rc(pre)) pre=rc(pre);
	rc(pre)=rc(u),fa(rc(u))=pre,fa(lc(u))=0,clear(u);
	update(pre),splay(pre);//这一次Splay可以解决祖先siz没更新的问题
}

查询\(v\)的排名

int getrank(int v){
	int u=root,ran=1,f=0;
	while(u){
		f=u;
		if(v>v(u)) ran+=siz(lc(u))+1,u=rc(u);//Right
		else u=lc(u);//Left
	}
	splay(f);
	return ran;
}

查询排名为\(ran\)的值

int getnum(int ran){
	int u=root;
	while(u){
		int sz=siz(lc(u))+1;
		if(sz==ran) break;
		else if(sz>ran) u=lc(u);
		else ran-=sz,u=rc(u);
	}
	splay(u);
	return v(u);
}

前驱

int pre(int u){return getnum(getrank(u)-1);}

后继

int nex(int u){return getnum(getrank(u+1));}

时间复杂度证明

先。。。咕掉吧

模板题 & Code

P3369 【模板】普通平衡树

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define N 100010
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
#define ch(x,y) tr[x].ch[y]
#define fa(x) tr[x].fa
#define v(x) tr[x].v
#define siz(x) tr[x].siz
using namespace std;
struct tree{
	int ch[2],siz,fa,v;
	void clear(){ch[0]=ch[1]=siz=fa=v=0;}
}tr[N];
int t,cnt,root;
void clear(int u){tr[u].clear();}
int newnode(int v){v(++cnt)=v,siz(cnt)=1;return cnt;}
void update(int u){siz(u)=siz(lc(u))+siz(rc(u))+1;}
bool get(int u){return u==rc(fa(u));}
void rot(int x){
	int y=fa(x),z=fa(y);//保证y!=0
	bool dir=get(x),tdir=get(y);
	if(ch(x,!dir)) fa(ch(x,!dir))=y;
	ch(y,dir)=ch(x,!dir);
	ch(x,!dir)=y;
	fa(y)=x,fa(x)=z;
	if(z) ch(z,tdir)=x;
	update(y),update(x);
}
void splay(int x){
	for(int f;(f=fa(x));rot(x))
		if(fa(f)) rot(get(f)==get(x)?f:x);
	root=x;
}
void ins(int v){
	int u=root,f=0;
	while(u) f=u,u=ch(u,v>v(u));//>在右，<=在左
	u=newnode(v),fa(u)=f;
	if(f) ch(f,v>v(f))=u;
	splay(u);
}
void del(int v){
	int u=root,f=0;
	while(v(u)!=v&&u) f=u,u=ch(u,v>v(u));
	if(!u){splay(f);return;}
	splay(u);
	int pre=lc(u);
	if(!pre){root=rc(u),fa(rc(u))=0,clear(u);return;}
	while(rc(pre)) pre=rc(pre);
	rc(pre)=rc(u),fa(rc(u))=pre,fa(lc(u))=0,clear(u);
	update(pre),splay(pre);
}
int getrank(int v){
	int u=root,ran=1,f=0;
	while(u){
		f=u;
		if(v>v(u)) ran+=siz(lc(u))+1,u=rc(u);//Right
		else u=lc(u);//Left
	}
	splay(f);
	return ran;
}
int getnum(int ran){
	int u=root;
	while(u){
		int sz=siz(lc(u))+1;
		if(sz==ran) break;
		else if(sz>ran) u=lc(u);
		else ran-=sz,u=rc(u);
	}
	splay(u);
	return v(u);
}
int pre(int u){return getnum(getrank(u)-1);}
int nex(int u){return getnum(getrank(u+1));}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		int op,x;
		cin>>op>>x;
		if(op==1) ins(x);
		else if(op==2) del(x);
		else if(op==3) cout<<getrank(x)<<"\n";
		else if(op==4) cout<<getnum(x)<<"\n";
		else if(op==5) cout<<pre(x)<<"\n";
		else if(op==6) cout<<nex(x)<<"\n";
	}
	return 0;
}

附：相同节点合并代码

也可以把值相同的节点合并为\(1\)个，用\(cnt\)记一下数。

然后newnode、update、ins、del、getrank、getnum函数需要做相应的修改。具体见代码。

#include<bits/stdc++.h>
#define int long long
#define N 100010
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
#define ch(x,y) tr[x].ch[y]
#define fa(x) tr[x].fa
#define v(x) tr[x].v
#define siz(x) tr[x].siz
#define cnt(x) tr[x].cnt
using namespace std;
struct tree{
	int ch[2],siz,fa,v,cnt;
	void clear(){ch[0]=ch[1]=siz=fa=v=0;}
}tr[N];
int t,cnt,root;
void clear(int u){tr[u].clear();}
int newnode(int v){v(++cnt)=v,siz(cnt)=1,cnt(cnt)=1;return cnt;}
void update(int u){siz(u)=siz(lc(u))+siz(rc(u))+cnt(u);}
bool get(int u){return u==rc(fa(u));}
void rot(int x){
	int y=fa(x),z=fa(y);//保证y!=0
	bool dir=get(x),tdir=get(y);
	if(ch(x,!dir)) fa(ch(x,!dir))=y;
	ch(y,dir)=ch(x,!dir);
	ch(x,!dir)=y;
	fa(y)=x,fa(x)=z;
	if(z) ch(z,tdir)=x;
	update(y),update(x);
}
void splay(int x){
	for(int f;(f=fa(x));rot(x))
		if(fa(f)) rot(get(f)==get(x)?f:x);
	root=x;
}
void ins(int v){
	int u=root,f=0;
	while(u&&v(u)!=v) f=u,u=ch(u,v>v(u));//>在右，<=在左
	if(u) cnt(u)++;
	else{
		u=newnode(v),fa(u)=f;
		if(f) ch(f,v>v(f))=u;
	}
	splay(u);
}
void del(int v){
	int u=root,f=0;
	while(v(u)!=v&&u) f=u,u=ch(u,v>v(u));
	if(!u){splay(f);return;}
	splay(u);
	if(cnt(u)>1){cnt(u)--;return;}
	int pre=lc(u);
	if(!pre){root=rc(u),fa(rc(u))=0,clear(u);return;}
	while(rc(pre)) pre=rc(pre);
	rc(pre)=rc(u),fa(rc(u))=pre,fa(lc(u))=0,clear(u);
	update(pre),splay(pre);
}
int getrank(int v){
	int u=root,ran=1,f=0;
	while(u){
		f=u;
		if(v>v(u)) ran+=siz(lc(u))+cnt(u),u=rc(u);//Right
		else u=lc(u);//Left
	}
	splay(f);
	return ran;
}
int getnum(int ran){
	int u=root;
	while(u){
		int sz=siz(lc(u))+cnt(u);
		//如果ran在[siz[l]+1,siz[l]+cnt[u]]的区间内，就说明第ran名就是u
		if(ran>=siz(lc(u))+1&&ran<=sz) break;
		else if(siz(lc(u))>=ran) u=lc(u);
		else ran-=sz,u=rc(u);
	}
	splay(u);
	return v(u);
}
int pre(int u){return getnum(getrank(u)-1);}
int nex(int u){return getnum(getrank(u+1));}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		int op,x;
		cin>>op>>x;
		if(op==1) ins(x);
		else if(op==2) del(x);
		else if(op==3) cout<<getrank(x)<<"\n";
		else if(op==4) cout<<getnum(x)<<"\n";
		else if(op==5) cout<<pre(x)<<"\n";
		else if(op==6) cout<<nex(x)<<"\n";
	}
	return 0;
}

标签：pre,ch,int,siz,笔记,Splay,fa,rc
From： https://www.cnblogs.com/Sinktank/p/18253323

相关文章

  • 2024/06/20笔记随笔
    Mysql常用工具表之间的链接查询：通过添加外键进行查询其中添加外键的表为从表；笛卡尔乘积（两张表所有数据相连--R表*S表）（笛卡尔乘积--S表的每个字段分别与R表的每个字段进行链接）：使用交叉乘积（）：SELECT✳FROMR表，S表；简化：SELECT✳FROMR表CROSSJOINS表；两张表链接查询：（外键数据之......
  • HieRec论文阅读笔记
    HieRec:HierarchicalUserInterestModelingforPersonalizedNewsRecommendation论文阅读笔记Abstract现存的问题：​ 用户兴趣建模对于个性化新闻推荐至关重要。现有的新闻推荐方法通常从每个用户以前的行为中学习一个单一的用户嵌入，以代表他们的整体兴趣。然而，用户兴趣通......
  • STM32学习笔记（十）--I2C、IIC总线协议详解
    概述：InterIntegratedCircuit，一组多从多组多从有应答是一种同步（具有时钟线需要同步时钟SCL）、串行（一位一位的往一个方向发送）、半双工（发送接收存在一种）通信总线。（1）硬件电路所有I2C设备的SCL连接在一起，SDA连在一起            设备的SCL和SDA均要......
  • Vitis Accelerated Libraries 学习笔记--OpenCV 安装指南
    目录1.简介2.安装过程2.1安装准备2.2常见错误2.2.1核心共享库报错3.通过实例测试 4.总结1.简介使用VitisVisionLibraryVitis视觉库，为什么要安装opencv库？在使用VitisVisionLibrary时，安装OpenCV库是因为许多视觉库的功能都提供了示例设计测试平台，使用......
  • Web之http学习笔记
    目录HTTPurlhttp请求请求行请求方法请求头请求正文http响应响应行状态码响应头响应正文Cookie定义：内容：用途：生命周期：隐私和安全性：Session实现原理组成：PHP中的Session设置函数session传输HTTPhttp文本传输协议（HyperTextTransferProtocol），遵循请求/响应（request/response）模型url......
  • 电路分析期末总结笔记上
    电流，电压定义及单位电流（Current）的定义是单位时间内通过导体横截面的电荷量。电压（Voltage），又称作电势差或电位差，是衡量单位电荷在静电场中由于电势不同而产生的能量差的物理量。 参考方向，关联参考概念U，I采用相同的参考方向，为正U，I采用不相同的参考方向，为负功率的计算......
  • 学习笔记STMF4 TIMER定时器（使用开发板立创天空星STMF4）
    目录                                                #定时器的介绍             #怎么去理解定时器的预分频系数                                        ......
  • [模式识别复习笔记] 第1-2章 基本概念
    1.模式识别系统的各个设计环节模式采集：借助物理设备（传感器、摄像头）进行数据的采集和存储。预处理：数据清洗、降噪，增强数据中有用的信息。特征提取：提取数据中对识别有用的特征。分类器学习：根据训练数据特点，选择何时的分类器模型，利用训练集学习得到参数。2.模式......
  • [模式识别复习笔记] 第3章 线性判别函数
    1.线性判别函数1.1定义在\(d\)维特征空间中，有线性判别函数：\[G(x)=w^{\text{T}}x+b\]其中，\(w=[w_1,w_2,\ldots,w_d]^T\)称为权值向量，\(b\)称为偏置，都是需要学习的参数。\(G(x)=0\)为决策边界方程。PS：只能解决二分类问题。1.2几何意义\(w\)为超......
  • [模式识别复习笔记] 第4章 SVM
    1.SVM简介1.1SVM支持向量机给定如图所示的线性可分训练集，能够将两类样本正确分开的直线很多。感知机算法可以找到一条直线，且找到的直线不唯一。然而感知机无法确定哪一条直线最优，但是\(\text{SVM}\)可以。\(\text{SVM}\)可以找到能够将训练样本正确分类的直线中具有......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99