首页 > 其他分享 >Splay

Splay

时间:2023-10-09 20:35:16浏览次数:27  
标签:splay ll tr Splay key now 节点

prologue

快 csps 了还什么也不会的一条费鱼。

下面是分别通过 acwing y总和樱雪喵学到的splay。


introduction

首先来了解一下二叉搜索树。二叉搜索树是一种二叉树的树形数据结构,其定义如下:

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

下面是我画出来的一棵二叉搜索树,很显然是满足上述性质的(注意,图上的点都是表示点权)。

image

插入节点

我们如果要插入一个节点,应该遵循上面的规则,这样才能保证这个二叉搜索树的结构是一直保持的:

  1. 如果比当前节点的权值大,则向这个节点的右子树遍历。直到叶子节点然后停止,插入该值。
  2. 如果比当前节点的权值小,则向这个节点的左子树遍历。直到叶子节点然后停止,插入该值。
  3. 如果和当前节点的权值相同,则可以考虑两种方案:
    • 直接在这个节点的下面进行连接。
    • 给这个权值的节点开一个维度 cnt,用来统计这个权值的个数。

从理论与结构来说,第一种明显是荒谬之谈,但是第一种往往在实际过程中会比第二种少很多的情况特判,操作起来上手舒服。(或许这就是为什么大部分学校把信息学归为工科的原因?)

删除节点

我们删除节点的操作往往会比较麻烦:

  1. 如果这个节点没有子树,则我们可以直接删除。
  2. 如果只有一个儿子,直接将这个儿子和它的父节点相连,然后删除这个点。(图解)
    image
  3. 如果有两个儿子,那么我们删除的过程就会变得比较麻烦。(下面为重建的新图)
    image
    • 删除 4 号节点。我们首先先将与 4 相连的边都删掉
      image

    • 然后我们用一边的儿子(任意都可,看你习惯,我来左边)与原来的父节点相连。
      image

    • 然后我们再按照搜索二叉树的原则,把右儿子给连接上。(图丑轻喷)
      image

这里我们就成功的删除了 4 号节点,并且同时维护了搜索二叉树的性质。

我们对于一个节点的查询是和这个搜索二叉树的树高有关系的。

但是我们其实可以很轻松的构造一种方案,让这个效率降成 \(O(n)\) 了,就是从根节点开始不断加比它大的数,这样子我们的树高就是点的个数,我们的效率也就低了下来。

为了让我们的时间复杂度有保证,我们就诞生了平衡树这一种数据结构。通过左旋(zag)和右旋(zig)来维护搜索二叉树的树高一直为 \(log_2 n\) 的。、

splay

zag & zig

首先我们得介绍清楚 zig 和 zag 的实现原理,否则后期难以进行。下面是摘自 oiwiki 上的图片。
左边通过右旋得到了右边,右边通过左旋得到了左边。

image

下面是对于左右旋的一个略详解:

右旋:将 \(A\) 的左孩子 \(B\) 向左上旋转,代替 \(A\) 成为根节点,将 \(A\) 结点向右下旋转成为 \(B\) 的右子树的根结点,\(B\) 的原来的右子树变为 \(A\) 的左子树。

左旋则是右旋的镜像操作。

(想了想还是把代码放在这里吧)

由于我们上面的左旋右旋都只和 x 是父亲的哪个儿子进行的方向进行判断。造作完成后,我们要更新节点的 size 信息。

#define ll int

inline void rotate(ll x)
{
	ll y = fa(x), z = fa(y), c = get(x); // x的爹在哪个方向
	if(tr[x].s[c ^ 1]) fa(tr[x].s[c^1]) = y // 把 x 相反方向的儿子接在y上,可以根据图解来联系理解。
	tr[y].s[c] = tr[x].s[c ^ 1], tr[x].s[c ^ 1] = y, fa(y) = x, fa(x) = z;
	if(z) tr[z].s[y == tr[z].s[1]] = x;
	maintain(y), maintain(x);
}

破坏平衡的几个形式

LL型

原因:左子树的左子树过长破坏平衡。 解决方案:右旋 zig。

image

RR型

原因:右子树的右子树过长破坏平衡性。 解决方案:左旋 zag。

image

L-R型

原因:左子树的右子树过长导致破坏平衡性。 解决方案:左右旋 zag-zig。

细说:先将左子树的右子树,通过左旋,变成左子树的左子树,即 LL 型,然后再右旋,达到平衡。

image

R-L型

原因:右子树的左子树过长导致破坏平衡性。 解决方案:右左旋 zig-
zag。

细说:先将右子树的左子树,通过右旋,变成了右子树的右子树,即 RR 型 然后再左旋,达到平衡。

image

splay操作

我们的 splay 操作就是要将上面几种方式给变成一个平衡的结构,实际上 splay 的代码实现很短。

#define ll int 
#define rl register ll 

inline void splay(ll x)
{
	for(rl f = fa(x); f = fa(x), f; rotate(x))
		if(fa(f)) rotate(get(f) == get(x) ? f : x);
	root = x;
}

为了保证 splay 的时间复杂度,我们规定每次最后访问到的节点是 x,都要把 x Splay 到根上。

时间复杂度分析

分析什么分析啊,计算机是工科!(just kidding,实际上是菜鱼不会分析
这里贴一个复杂度证明想了解的神仙可以自行学习。知道这个复杂度是 \(logn\) 的就行了。

应用

之后就是一些查询插入修改访问之类的了,和二叉搜索树基本上没有多大关联了。

这里一个操作一个操作的展开。

插入

其实本质的思路和二叉搜索树没有多大的区别,主要是最后要 splay 一下维护我们平衡树的结构。

#define ll int 
#define rl register ll 

inline void insert(ll key)
{
	ll now = rt,  f = 0;
	while(now) f = now, now = tr[now].s[key>tr[now].key];
	now = newnode(key), fa(now) = f, tr[f].s[key>tr[now].key] = now, splay(now);
}

删除

前面已经说过了二叉搜索树是怎么样实现删除操作的,下面直接放代码了。

inline void delete(ll key)
{
	ll now = root, p = 0;
	while(tr[now].key != key && now) p = now, now = tr[now].s[key>tr[now].key]; // 找到要删除的节点
	if(!now) { splay(p); return ; }
	splay(now), ll cur = ls(now);
	if(!cur) { rt = rs(now), fa(rs(now))=0, clear(now); return ; } 
	while(rs(cur)) cur = rs(cur);
	rs(cur) = rs(now), fa(rs(now)) = cur, fa(ls(now)) = 0, clear(now); // 把右儿子接在(左子树的最大权值)下面
	maintain(cur), splay(cur);
}

查询 x 的排名

从根节点开始,根据左子树的 \(size\) 判断我们查询的 \(x\) 在哪棵子树里面;因为一个平衡树里可能有一堆权值是 \(x\) 的点,这里我们本质上是要找到严格小于 \(x\) 的点数 + 1。

每次都往右子树走,左边的子树就给答案贡献了 \(size_ls(now) + 1\) 个比 \(x\) 要小的数。

#define ll long long 
#define rl register ll 

inline ll rank(ll key)
{
	ll res = 1, now = root, p;
	while(now)
		if(p = now, tr[now].key < key) res += tr[ls(now)].size + 1, now = rs(now);
		else now = ls(now);
	
	return splay(p), res;
}

注意,这里虽然只在树上跑点,没有改变数的结构,但任然要 splay(把splay这个操作当成施法后摇就行了)

查询排名为 k 的数

同理,根据子树 \(size\) 直接判断排名为 \(k\) 的数走哪一边。

#define ll long long 
#define rl register ll 

inline void get_key_by_rank(ll rk)
{
	ll now = root;
	while(now) 
	{
		ll sz = tr[ls(now)].size + 1;
		if(sz > rk) now = ls(now);
		else if(sz == rk) break;
		else if(sz < rk) rk -= sz, now = rs(now);
	}
	return splay(now), tr[now].key;
}

查询 x 的前驱

从根节点开始往下走,如果当前点大于等于 x,那么这个的前驱就一定在左子树,我们就往左走;否则,前驱可能在这个点或者在右子树,这个时候我们先用这个节点更新答案,然后再去这个节点的右子树继续找。

#define ll long long
#define rl register ll 

inline ll pre(ll key)
{
	ll now = root, ans = 0, p;
	while(now)
		if(p = now, tr[now].key >= key) now = ls(now);
		else ans = tr[now].key, now = rs(now);
	return splay(p), ans;
}

查询 x 的后继

把前去操作倒过来就好了。

#define ll long long
#define rl register ll

inline ll  suf(ll key)
{
	ll now = root, ans = 0, p;
	while(now)
		if(p = now, tr[now].key <= key) now = rs(now);
		else ans = tr[now].key, now = ls(now);
	return splay(p), ans;
}

完整版的板子

点击查看代码

一些上面操作的复合版本

这里的 \(splay(a, b)\) 是指的将 a 一路翻转到 b 的下面。

inline void splay(ll x, ll y)
{
	for(rl f=fa(x);f=fa(x), f != y; rotate(x))
		if(fa(f) != y) rotate(get(f) == get(x) ? f : x);
	if(!y) root = x;
}

将一个序列插入到 y 的后面

  1. 找到 y 的后继 z。
  2. 将 y 旋转到根节点。splay(y, 0);
  3. 将 z 转到 y 的下面。 splay(z, y);
  4. 将序列加在 z 的左子树下。

删除 \([l, r]\) 这一段

  1. 找到 l 的前驱 a, 找到 r 的后继 b。
  2. 将 a 转到根,将 b 转到 根的下面。
  3. 此时,b 的左子树就是 \([l, r]\) 就是我们要删除的区间。直接将 b 的左子树清空行了。

find函数

找到下标为 x 的点,原理和二叉搜索树的找排名为 k 的函数相同。注意!我们因为在进行递归操作的时候要一边去找然后一边区 pushdown。同时因为我们会有一个虚点所以最后找到的排名是实际的下标 + 1。

inline ll find(ll x)
{
	ll now = root, x ++ ;
	while(now)
	{
		pushdonw(now); ll sz = tr[ls(now)].size + 1;
		if(sz == x) break;
		else if(sz > x) now = ls(now);
		else now = rs(now), x -= sz;
	}
	return now;
}

reverse

inline void reverse(ll l, ll r)
{
	ll x = find(l - 1); splay(x, 0);
	ll y = find(r + 1); splay(y, x);
	tr[ls(y)].lz ^= 1;
}

build

inline void build()
{
	root = newnode(0); ll now = root;
	for(rl i=1; i <= n + 1; ++ i, now = rs(now)) tr[now].size = n + 3 - i, rs(now) = newnode(a[i]), fa(rs(now)) = now;
}

输出

我们的平衡树一直就是维护的一个中序遍历,所以只需要中序遍历就能够输出出来原序列。

inline void write(ll now)
{
	pushdown(now);
	if(ls(now)) write(ls(now));
	if(tr[now].key) cout << tr[now].key << endl;
	if(rs(now)) write(rs(now));
}

标签:splay,ll,tr,Splay,key,now,节点
From: https://www.cnblogs.com/carp-oier/p/17752131.html

相关文章

  • display:none和overflow:hidden的区别
    1、display:none当将一个元素的display属性设置为none时,该元素将不会显示在网页中,并且不会占据任何空间。也就是说,该元素会完全隐藏,其他的元素会立即占据它原来的位置。该属性适用于需要完全隐藏某个元素的场景。//html代码:完全隐藏子元素<divclass="father"><di......
  • Go - Parsing Time Displays Into Structs
     funcmain(){str:="4:31am+0800onOct1,2021"layout:="3:04pm-0700onJan2,2006"t,err:=time.Parse(layout,str)iferr!=nil{log.Println("C......
  • display none 和 opacity 0 二者的区别辨析
    HTML属性display:none和opacity:0在Accessibility(无障碍性)处理上有明显的区别,它们分别用于不同的场景,并对网页元素的可见性和交互性产生不同的影响。在本文中,我将详细解释这两个属性的作用、区别以及何时使用它们,并提供示例来说明它们的效果。display:none和opacity:0......
  • jQuery中hide()和display的区别在于它们实现元素隐藏的方式不同。
    1.hide()方法是jQuery提供的一个函数,用于隐藏元素。当使用hide()方法时,元素会被设置为display:none,即不显示在页面上,但仍然占据着原来的空间。隐藏后的元素可以通过调用show()方法来重新显示。示例代码:$("#elementId").hide();//隐藏元素$("#elementId").show();//显示......
  • 比较 opacity: 0、visibility: hidden、display: none
    结构display:none:会让元素完全从渲染树中消失,渲染的时候不占据任何空间,不能点击,visibility:hidden:不会让元素从渲染树消失,渲染元素继续占据空间,只是内容不可见,不能点击opacity:0:不会让元素从渲染树消失,渲染元素继续占据空间,只是内容不可见,可以点击继承display:none和op......
  • display: none与visibility: hidden的区别
    display:none与visibility:hidden的区别引言:在前端面试中,一般比较侧重JavaScript方面的考察,CSS布局方面考察的内容会相对少一些,其中display:none与visibility:hidden的区别是较常见的考点,这两个css配置都可以从视觉上隐藏DOM元素,那这两者的使用上有什么区别呢?display:none......
  • 17 display 和 浮动
    display可以使得行内元素和块元素相互转换,但不常用,用float!<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><style>/*inline:block:i......
  • python报错:pyglet.canvas.xlib.NoSuchDisplayException: Cannot connect to "None"
    运行python代码报错:       问题发现:问题其实十分的狗血,这个代码是在服务器上运行的,运行之前其实并没有看具体的代码情况,gitclone下载下来就直接运行了,原来这个代码需要进行图片绘制,说直白些就是需要显示屏,于是解决方法也十分简单,就是换个带桌面的电脑或者使用......
  • Python中的​​display​​​函数 from IPython.display import display
    Python中的display函数通常与JupyterNotebook或其他交互式开发环境一起使用,用于显示各种类型的数据,包括文本、图像、音频、视频等。这个函数通常是由IPython.display模块提供的,主要用于创建富媒体输出,以便在笔记本中直观地呈现数据。以下是有关display函数的一些重要信息:导入模块:......
  • Splay学习笔记
    这已经是第三次学习Splay了图片内容转载自yyb的博客二叉搜索树本来是一颗二叉树,但是满足这样的条件:对于一个节点\(x\),满足它的左子树中所有节点的\(val\)都小于\(val_x\),右子树中的所有节点的\(val\)都大于\(val_x\)。那么很显然,我们最希望它(尽可能)是一颗满二......