首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

关于 Splay 树

编程知识
2024年09月11日 13:00

前置芝士

$\LARGE {关于二叉搜索树及平衡树无聊的一大串子定义}$

二叉搜索树(BST树)

定义

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  • 空树是二叉搜索树。

  • 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

  • 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

  • 二叉搜索树的左右子树均为二叉搜索树。

复杂度

二叉搜索树上的基本操作所花费的时间与这棵树的高度成\(\color{#40c0bb}{正比}\)。对于一个有 \(n\) 个结点的二叉搜索树中，这些操作的最优时间复杂度为 \(O(\log n)\)，最坏为 \(O(n)\)。随机构造这样一棵二叉搜索树的\(\color{#40c0bb}{期望高度}\)为 \(O(\log n)\)。

性质

其实也就是定义

设 \(x\) 是二叉搜索树中的一个结点。

如果 \(y\) 是 \(x\) 左子树中的一个结点，那么 \(y.key≤x.key\)。

如果 \(y\) 是 \(x\) 右子树中的一个结点，那么 \(y.key≥x.key\)。

在二叉搜索树中：

  1. 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。

  2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。

  3. 任意结点的左、右子树也分别为二叉搜索树。

用途

二叉搜索树通常可以高效地完成以下操作：

  1. 查找最小/最大值

  2. 搜索元素

  3. 插入一个元素

  4. 删除一个元素

  5. 求元素的排名

  6. 查找排名为 k 的元素

平衡树

定义

由二叉搜索树的复杂度分析可知：操作的复杂度与树的高度 \(h\) 有关。

那么我们可以通过一定操作维持树的高度（平衡性）来降低操作的复杂度，这就是\(\color{#40c0bb}{平衡树}\)。

\(\color{#40c0bb} \large \textbf{平衡性}\)
通常指每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 \(1\)。

平衡的调整过程——树旋转

定义

树旋转是在二叉树中的一种子树调整操作， 每一次旋转并\(\color{#40c0bb}{不影响}\)对该二叉树进行\(\color{#40c0bb}{中序遍历}\)的结果。
树旋转通常应用于需要调整树的局部平衡性的场合。树旋转包括两个不同的方式，分别是\(\color{#40c0bb}{左旋(Left　Rotate　或者 　zag)}\)和 \(\color{#40c0bb}{右旋(Right　Rotate　或者　zig)}\)。 两种旋转呈镜像，而且互为逆操作。

具体操作

右旋

对于结点 \(A\) 的右旋操作是指：将 \(A\) 的左孩子 \(B\) 向右上旋转，代替 \(A\) 成为根节点，将 \(A\) 结点向右下旋转成为 \(B\) 的右子树的根结点，\(B\) 的原来的右子树变为 \(A\) 的左子树。

左旋

完全同理

具体情况

其实你只需要知道二叉搜索树的几条基本性质即可：

  1. 每个结点都满足左子树的结点的值都小于自己的值，右子树的结点的值都大于自己的值，左右子树也是二叉搜索树。

  2. 中序遍历二叉搜索树可以得到一个由这棵树的所有结点的值组成的有序序列。（即所有的值排序后的结果）

正片

背景

不难发现\(BST树\)的一种极端情况：\(\color{#40c0bb}{退化情况}\)

这种毒瘤数据让时间复杂度从\(O(log(n))\)退化到了恐怖的\(O(n)\)

于是就有各种各样的科学家们，开始思考人生，丧心病狂地创造出了各种优化BST的方法...

Splay

定义

啥是\(Splay\)？
她实际上就是一种可以旋转的平衡树。
她可以通过Splay/伸展操作不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊 \(O(\log n)\) 时间内完成插入，查找和删除操作，并且保持平衡而不至于退化成链。

原理&实现

节点维护信息

rt tot fa[N] ch[N][2] val[N] cnt[N] sz[N]
根 节点编号 父节点 子节点 左0右1 权值 节点大小 子树大小

基本操作

首先你要了解的就是一些基本操作：

  • \(maintain(x)\)：在改变节点位置后，将节点 \(x\) 的 \(\text{size}\) 更新。
  • \(get(x)\)：判断节点 \(x\) 是父亲节点的左儿子还是右儿子。
  • \(clear(x)\)：清空节点 \(x\)。

void maintain(int x){
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
	
bool get(int x){
	return x==ch[fa[x]][1];
}
	
void clear(int x){
	ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
}

很简单对吧？

接下来可就要上难度了。

旋转操作(rotate)

由定义可知，我们要将某个节点旋转到根节点。

而要想知道怎么将一个节点旋转到根节点，首先要考虑怎么将她旋转到父亲节点。

当该节点为左儿子时

如图，方框表示子树，圆框表示节点

现在，我们要将 \(x\) 节点往上爬一层到他的父节点 \(y\) ，为了保证不改变中序遍历顺序，我们可以让 \(y\) 成为 \(x\) 的右儿子。

但是原来的 \(x\) 节点是有右儿子 \(B\) 的，显然我们要把 \(B\) 换一个位置才能达到目的。

我们知道： \(x\) 节点的右子树必然是大于 \(x\) 节点的； \(y\) 节点必然是大于 \(x\) 节点的右子树和 \(x\) 节点本身的（因为 \(x\) 节点及其右子树都是原来 \(y\) 的左子树，肯定比 \(y\) 小（根据二叉搜索树性质））

因此我们可以把 \(x\) 节点原来的右子树放在 \(y\) 的左儿子的位置上，达成目的。

实际上，这也就是\(\color{#40c0bb}\textbf{右旋}\)的原理。

当该节点为右儿子时

原理相同。

旋转为

通解

若节点 \(x\) 为 \(y\) 节点的位置 \(z\)(\(z=0\) 为左节点，\(z=1\) 为右节点 )

  1. 将 \(y\) 节点放到 \(x\) 节点的 \(z \oplus 1\) 的位置.(也就是, \(x\) 节点为 \(y\) 节点的右子树,那么 \(y\) 节点就放到左子树, \(x\) 节点为 \(y\) 节点左子树,那么 \(y\) 节点就放到右子树位置)

  2. 如果说 \(x\) 节点的 \(z \oplus 1\) 位置上,已经有节点,或者一棵子树,那么我们就将原来 \(x\) 节点 \(z \oplus 1\) 位置上的子树,放到 \(y\) 节点的位置 \(z\) 上面.

这里有个小口诀：“左旋拎右左挂右，右旋拎左右挂左”

看懂文字了，就可以尝试理解一下代码了。

实现

void rotate(int x){
	int y=fa[x],z=fa[y],chk=get(x);
    //y为x的父亲，z为x的爷爷，chk判断x是左儿子还是右儿子

	ch[y][chk]=ch[x][chk^1];
	if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
	ch[x][chk^1]=y;
	fa[y]=x;
	fa[x]=z;
	if(z) ch[z][y==ch[z][1]]=x;
	maintain(y),maintain(x);
}

Splay操作

Splay(x,to) 是要将 \(x\) 节点旋转至 \(to\) 节点。

单旋

很暴力的办法，对于 \(x\) 节点，每次上旋至 \(fa[x]\) ，直到 \(to\) 节点。

但是，如果你真的这么写可能会T成SB被某些毒瘤数据卡成 \(n^2\)

所以不要看单旋简单好写，这里更推荐双旋的写法。

双旋

双旋的优化在于：

  1. 如果当前处于共线状态的话，那么先旋转 \(y\) ，再旋转 \(x\) 。这样可以强行让他们不处于共线状态，然后平衡这棵树.

  2. 如果当前不是共线状态的话，那么只要旋转 \(x\) 即可。

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

查找操作

当然你也可以不写。

查找操作是因为查 \(k\) 的前驱后继时需要将 \(k\) 旋到根节点的位置。

实际上你也可以直接 splay(k,0) 或先插入 \(k\) 查询后再将它删去。

Splay也是一颗二叉搜索树，因此满足左侧都比他小，右侧都比他大。

因此只需要相应的往左/右递归即可。

void find(int x){
    int u=root;
    if(!u)return;//树空
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}

插入操作

  • 如果树空了，则直接插入根并退出。
  • 如果当前节点的权值等于 \(k\) 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
  • 否则按照二叉查找树的性质（左侧都比他小，右侧都比他大）向下找，找到空节点就插入即可。
void ins(int k){//insert
	if(!rt){
		val[++tot]=k;
		cnt[tot]++;
		rt=tot;
		maintain(rt);
		return;
	}
	int cur=rt,f=0;
	while(1){
		if(val[cur]==k){
			cnt[cur]++;
			maintain(cur);
			maintain(f);
			splay(cur);
			break;
		}
		f=cur;
		cur=ch[cur][val[cur]<k];
		if(!cur){
			val[++tot]=k;
			cnt[tot]++;
			fa[tot]=f;
			ch[f][val[f]<k]=tot;
			maintain(tot);
			maintain(f);
			splay(tot);
			break;
		}
	}
}

查询 \(x\) 的排名

  • 如果 \(x\) 比当前节点的权值小，向其左子树查找。
  • 如果 \(x\) 比当前节点的权值大，将答案加上左子树（\(size\)）和当前节点（\(cnt\)）的大小，向其右子树查找。
  • 如果 \(x\) 与当前节点的权值相同(已存在)，将答案加 \(1\) 并返回。
int rk(int k){//the rank of "k"
	int res=0,cur=rt;
	while(1){
		if(k<val[cur]){
			cur=ch[cur][0];
		}else{
			res+=sz[ch[cur][0]];
			if(!cur) return res+1;
			if(k==val[cur]){
				splay(cur);
				return res+1;
			}
			res+=cnt[cur];
			cur=ch[cur][1];
		}
	}
}

查询排名 \(x\) 的数

  • 如果左子树非空且剩余排名 \(k\) 不大于左子树的大小 \(size\)，那么向左子树查找。
  • 否则将 \(k\) 减去左子树的和根的大小。如果此时 \(k\) 的值小于等于 \(0\)，则返回根节点的权值，否则继续向右子树查找。
int kth(int k){//the number whose rank is "k"
	int cur=rt;
	while(1){
		if(ch[cur][0] && k<=sz[ch[cur][0]]){
			cur=ch[cur][0];
		}else{
			k-=cnt[cur]+sz[ch[cur][0]];
			if(k<=0){
				splay(cur);
				return val[cur];
			}
			cur=ch[cur][1];
		}
	}
}

查询前驱&后继

前驱就是 \(x\) 的左子树中最右边的节点

后继就是 \(x\) 的右子树中最左边的节点

前驱

int pre(){//precursor
	int cur=ch[rt][0];
	if(!cur) return cur;
	while(ch[cur][1]) cur=ch[cur][1];
	splay(cur);
	return cur;
}

后继

其实就是查前驱的反面

int nxt(){//next or successor
	int cur=ch[rt][1];
	if(!cur) return cur;
	while(ch[cur][0]) cur=ch[cur][0];
	splay(cur);
	return cur;
}

查前驱后继有好多种写法，如果想偷懒只写一遍就可以酱紫

int prenxt(int x,int k){//0 pre 1 nxt
	find(x);
	int cur=rt;
	if(!k && val[cur]<x) return cur;
	if(k && val[cur]>x) return cur;
	cur=ch[cur][k];
	while(ch[cur][!k]){
		cur=ch[cur][!k];
	}
	return cur;
}

删除操作

首先将 \(x\) 旋转到根的位置。

  • 如果 \(cnt[x]>1\)（有不止一个 \(x\)），那么将 \(cnt[x] - 1\) 并退出。

  • 否则，合并它的左右两棵子树即可。

void del(int k){//delete
	rk(k);
	if(cnt[rt]>1){
		cnt[rt]--;
		maintain(rt);
		return;
	}
	if(!ch[rt][0] && !ch[rt][1]){//树空
		clear(rt);
		rt=0;
		return;
	}
	if(!ch[rt][0]){
		int cur=rt;
		rt=ch[rt][1];
		fa[rt]=0;
		clear(cur);
		return;
	}
	if(!ch[rt][1]){
		int cur=rt;
		rt=ch[rt][0];
		fa[rt]=0;
		clear(cur);
		return;
	}
	int cur=rt,x=pre();
	fa[ch[cur][1]]=x;
	ch[x][1]=ch[cur][1];
	clear(cur);
	maintain(rt);
}

那么恭喜你，你已经学完了Splay的基本操作。

至于区间翻转什么的...

下次丕定

Code

Elaina's Code 
struct Slpay{
	int rt;//根 
	int tot;//节点编号 
	int fa[N];//父节点 
	int ch[N][2];//子节点 左0右1 
	int val[N];//权值 
	int cnt[N];//节点大小 
	int sz[N];//子树大小 
	
	void maintain(int x){
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
	}
	
	bool get(int x){
		return x==ch[fa[x]][1];
	}
	
	void clear(int x){
		ch[x][0]=ch[x][1]=fa[x]=val[x]=sz[x]=cnt[x]=0;
	}
	
	
	void rotate(int x){
		int y=fa[x],z=fa[y],chk=get(x);
		ch[y][chk]=ch[x][chk^1];
		if(ch[x][chk^1]) fa[ch[x][chk^1]]=y;
		ch[x][chk^1]=y;
		fa[y]=x;
		fa[x]=z;
		if(z) ch[z][y==ch[z][1]]=x;
		maintain(y);
		maintain(x);
	}
	
	void splay(int x,int goal=0){
		if(goal==0) rt=x;
		while(fa[x]!=goal){
			int f=fa[x];
			if(fa[fa[x]]!=goal){
				rotate(get(x)==get(f)?f:x);
			}
			rotate(x);
		}
	}
	
	void ins(int k){//insert
		if(!rt){
			val[++tot]=k;
			cnt[tot]++;
			rt=tot;
			maintain(rt);
			return;
		}
		int cur=rt,f=0;
		while(1){
			if(val[cur]==k){
				cnt[cur]++;
				maintain(cur);
				maintain(f);
				splay(cur);
				break;
			}
			f=cur;
			cur=ch[cur][val[cur]<k];
			if(!cur){
				val[++tot]=k;
				cnt[tot]++;
				fa[tot]=f;
				ch[f][val[f]<k]=tot;
				maintain(tot);
				maintain(f);
				splay(tot);
				break;
			}
		}
	}
	
	int rk(int k){//the rank of "k"
		int res=0,cur=rt;
		while(1){
			if(k<val[cur]){
				cur=ch[cur][0];
			}else{
				res+=sz[ch[cur][0]];
				if(!cur) return res+1;
				if(k==val[cur]){
					splay(cur);
					return res+1;
				}
				res+=cnt[cur];
				cur=ch[cur][1];
			}
		}
	}
	
	int kth(int k){//the number whose rank is "k"
		int cur=rt;
		while(1){
			if(ch[cur][0] && k<=sz[ch[cur][0]]){
				cur=ch[cur][0];
			}else{
				k-=cnt[cur]+sz[ch[cur][0]];
				if(k<=0){
					splay(cur);
					return val[cur];
				}
				cur=ch[cur][1];
			}
		}
	}
	
	int pre(){//precursor
		int cur=ch[rt][0];
		if(!cur) return cur;
		while(ch[cur][1]) cur=ch[cur][1];
		splay(cur);
		return cur;
	}
	
	int nxt(){//next or successor
		int cur=ch[rt][1];
		if(!cur) return cur;
		while(ch[cur][0]) cur=ch[cur][0];
		splay(cur);
		return cur;
	}
	
	void del(int k){//delete
		rk(k);
		if(cnt[rt]>1){
			cnt[rt]--;
			maintain(rt);
			return;
		}
		if(!ch[rt][0] && !ch[rt][1]){
			clear(rt);
			rt=0;
			return;
		}
		if(!ch[rt][0]){
			int cur=rt;
			rt=ch[rt][1];
			fa[rt]=0;
			clear(cur);
			return;
		}
		if(!ch[rt][1]){
			int cur=rt;
			rt=ch[rt][0];
			fa[rt]=0;
			clear(cur);
			return;
		}
		int cur=rt,x=pre();
		fa[ch[cur][1]]=x;
		ch[x][1]=ch[cur][1];
		clear(cur);
		maintain(rt);
	}


    void find(int x){
		int cur=rt;
		if(!cur) return;
		while(ch[cur][x>val[cur]]&&x!=val[cur]){
			cur=ch[cur][x>val[cur]];
		}
		splay(cur,0);
	}
	
	int get_pre(int x){
		find(x);
		int cur=rt;
		if(val[cur]<x) return cur;
		cur=ch[cur][0];
		while(ch[cur][1]){
			cur=ch[cur][1];
		}
		return cur;
	}
	
	int get_nxt(int x){
		find(x);
		int cur=rt;
		if(val[cur]>x) return cur;
		cur=ch[cur][1];
		while(ch[cur][0]){
			cur=ch[cur][0];
		}
		return cur;
	}

    int prenxt(int x,int k){//0 pre 1 nxt
		find(x);
		int cur=rt;
		if(!k && val[cur]<x) return cur;
		if(k && val[cur]>x) return cur;
		cur=ch[cur][k];
		while(ch[cur][!k]){
			cur=ch[cur][!k];
		}
		return cur;
	}
}tr;

signed main(){
	int m=rd;
	while(m--){
		int opt=rd,x=rd;
		if(opt==1){
			tr.ins(x);
		}else if(opt==2){
			tr.del(x);
		}else if(opt==3){
			printf("%lld\n",tr.rk(x));
		}else if(opt==4){
			printf("%lld\n",tr.kth(x));
		}else if(opt==5){
			tr.ins(x),printf("%lld\n",tr.val[tr.pre()]),tr.del(x);
		}else{
			tr.ins(x),printf("%lld\n",tr.val[tr.nxt()]),tr.del(x);
		}
	}
	return Elaina;
}

学了这么久 奖励你张图吧

才不是我自己想看

From:https://www.cnblogs.com/Elaina-0/p/18275500
本文地址: http://www.shuzixingkong.net/article/1943
0评论
提交 加载更多评论
其他文章 区块链应用与以太坊的交互
title: 区块链应用与以太坊的交互 author: ivhu date: 2024-09-11 15:52:13 categories: - 区块链 - 二层 tags: - 以太访 - L2 - 合约交互 - arbitrum description: 我们要谈的交互 首先要明确一点，以太坊是
区块链应用与以太坊的交互 区块链应用与以太坊的交互
.NET 6.0 + WPF 使用 Prism 框架实现导航
前言 Prism 一个开源的框架，专门用于开发可扩展、模块化和可测试的企业级 XAML 应用程序，适用于 WPF（Windows Presentation Foundation）和 Xamarin Forms 等平台。 Prism 基于 MVVM（Model-View-ViewModel）设计模式，
.NET 6.0 + WPF 使用 Prism 框架实现导航 .NET 6.0 + WPF 使用 Prism 框架实现导航 .NET 6.0 + WPF 使用 Prism 框架实现导航
verilog vscode 与AI 插件
Verilog 轻量化开发环境 背景 笔者常用的开发环境 VIAVDO, 体积巨大，自带编辑器除了linting 能用，编辑器几乎不能用，仿真界面很友好，但是速度比较慢。 Sublime Text, 非常好用的编辑器，各种插件使用verilog 非常方便，可以自动补全、生成调用、linting等；
verilog vscode 与AI 插件 verilog vscode 与AI 插件 verilog vscode 与AI 插件
一文快速上手-Vue CLI脚手架
安装Vue CLI (1) 全局安装Vue CLI 方式一（推荐方式）：在终端安装指定版本 npm i @vue/cli@5.0.8 -g 注：目前5.0.8应该是最新的版本了。 方式二：在终端通过命令安装最新版本 npm i @vue/cli -g (2) 升级Vue CLI到最新版本（可选） n
 SPiT：超像素驱动的非规则ViT标记化，实现更真实的图像理解 | ECCV 2024
Vision Transformer(ViT) 架构传统上采用基于网格的方法进行标记化，而不考虑图像的语义内容。论文提出了一种模块化的超像素非规则标记化策略，该策略将标记化和特征提取解耦，与当前将两者视为不可分割整体的方法形成了对比。通过使用在线内容感知标记化以及尺度和形状不变的位置嵌入，与基于图像
SPiT：超像素驱动的非规则ViT标记化，实现更真实的图像理解 | ECCV 2024 SPiT：超像素驱动的非规则ViT标记化，实现更真实的图像理解 | ECCV 2024 SPiT：超像素驱动的非规则ViT标记化，实现更真实的图像理解 | ECCV 2024
006.MinIO基础使用
图形界面基础使用 bucket bucket创建 图形界面创建bucket。 特性： Versioning 开启版本控制，开启版本控制则允许在同一键下保持同一对象的多个版本。 Object Locking 对象锁定防止对象被删除，需要支持保留和合法持有，只能在创建桶时启用。 Quita 配额限制bu
006.MinIO基础使用 006.MinIO基础使用 006.MinIO基础使用
AI实战 | 领克汽车线上营销助手：全面功能展示与效果分析
本篇文章的主要目的是为大家提供实现思路，以及如何更好地开发一个助手，而不仅仅是简单地进行拆解。如果采取拆解的方式，一篇文章可能会长达2万+字，还需要配以数十张图片，这将会非常繁琐。因此，针对拆解的详细内容，我计划单独制作一期视频，以帮助大家更清晰地理解。感谢大家对小雨的关注与支持。
AI实战 | 领克汽车线上营销助手：全面功能展示与效果分析 AI实战 | 领克汽车线上营销助手：全面功能展示与效果分析 AI实战 | 领克汽车线上营销助手：全面功能展示与效果分析
浅谈 C# 中的顶级语句
前言 在C# 9版本中引入了一项新特性：顶级语句，这一特性允许在不显式定义 Main 方法的情况下直接编写代码。 传统的写法 namespace&#160;TestStatements{ internal&#160;class&#160;Program { static&#160;void&#160
浅谈 C# 中的顶级语句 浅谈 C# 中的顶级语句
本站由星云主机提供云计算服务

网站建设一条龙服务、小程序开发、企业网站建设、定制开发，网络安全检测与维护 业务合作联系QQ:九六九五七三七