• 周二. 6月 25th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Splay入门

admin

11月 28, 2021

0. 前言

前置知识:二叉查找树。

我们知道,二叉查找树是会被恶意数据卡成(O(n^2))的。(如下图)

这很显然不是我们想要的,我们需要找到一种方法来让树保持平衡。
于是我们就有了各式各样的平衡树,而在OI中应用最为广泛的就是Splay和fhq_treap了,
并且这两个数据结构互相不能替代。
Splay:码量一般,常数较大,能够进行序列操作,LCT的专用树,不能可持久化。
fhq_treap:码量一般,常数较大,能够进行序列操作,维护LCT的时间复杂度多一只log,可以可持久化。
总而言之,一般来说学这两个就够了(

1. 树旋转

Splay使用树旋转来保持平衡。所以说我们要先学会树旋转。
如下图,我们只关心框出的子树。容易证明,这种操作没有破坏BST的性质。
我们称下图中的左旋为”将x旋转到父节点”,右旋为”将f旋转到父节点”。
换言之,旋转谁就是说将哪个节点提升到其父节点的位置。

不妨用( ext{connect}(u,v))表示连接(u,v),且(v)(u)的父亲。(u,v)原有的父子关系被删除。
记节点(x)的父亲为(f),祖父为(g)(x)的靠近(f)的儿子为(u)(这里指图中的B/B’),并且现在要旋转节点(x)
可以分为以下三步:

  1. ( ext{connect}(u,f))
  2. ( ext{connect}(x,g))
  3. ( ext{connect}(f,x))

图上看就是这样:

2. 单旋”spaly”

接下来我们介绍单旋的写法,也被称为”spaly”,复杂度是假的。

3. 双旋splay

4. 代码的简化

《Splay入门》有一个想法
  1. Wow, wonderful weblog layout! How long have you ever been running a blog
    for? you made running a blog look easy. The whole look
    of your website is magnificent, let alone the content material!
    You can see similar here sklep internetowy

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注