RainAir
My OI Blog
RainAir
平衡树学习笔记

定义

什么叫平衡树?就是看起来很平衡的树。

它是一种中序遍历有序的一棵搜索树,满足左儿子的权值<自身权值<右儿子的权值

它是递归定义的。

算法

目前平衡树的算法很多,在OI中,我们常使用TreapSplay<(set)

平衡的概念有高度平衡,重量平衡等。

高度平衡是指对于一个大小为N的树,深度不超过 $log_{ \frac{1}{\alpha} } (N + 1)​$

大小平衡是指对于一个数,满足:$ max (left,weight,right.weight)\leq \alpha \cdot weight $

对于高度平衡,所有平衡树算法几乎都满足,而Treap 替罪羊树还能同时满足重量平衡。

那么怎么调节平衡呢?我们通过旋转来调节。请看下图

https://blog.aor.sd.cn/wp-content/uploads/2018/11/rotate.jpg

其实究竟是左旋还是右旋不必搞那么清楚,可以按照自己的理解来,我的理解就是将左边的结点向右提就是右旋。

Treap

Treap 是一个平衡树

它在维护数据 key 的同时,维护了一个额外数据 weight

weight 是纯随机的数据,保证 key 满足平衡树的同时,weight满足一个堆.如下图就是一个Treap的形式:

https://blog.aor.sd.cn/wp-content/uploads/2018/11/74F1047C-8295-410E-9D2D-471619011A4D.png

Treap支持在 $log_2N$ 的时间复杂度内完成插入,删除,查询等操作。

插入

我们先按照二叉树的方式插入,如果Treap的性质被破坏,那么就通过旋转来维护Treap的性质。以下为插入图解:

https://blog.aor.sd.cn/wp-content/uploads/2018/11/treap1.jpg

先直接添加,然后发现违反了Treap的性质,所以旋转

https://blog.aor.sd.cn/wp-content/uploads/2018/11/treap2.jpg

一直旋转,直至旋转到根。

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap3.jpg

这样插入操作就结束了。

删除

因为删去一个叶子节点完全不破坏 Treap 的性质,不断尝试将根节点旋转
到叶子节点,然后删之即可(也可以认为根节点的权值变为+∞)

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap4.jpg

开始向下旋转

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap5.jpg

继续旋转,保持Treap性质

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap6.jpg

旋转

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap7.jpg

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Treap8.jpg

移除,这样删除操作就完成了。

代码实现

普通平衡树为例

Splay

Splay 维护平衡不需要额外的数据,其基本思路是数据访问的”二八规则“—— 80% 的人只用到 20% 的数据,所以有些常用的数据应当位于比较浅的位置
所以每次访问到一个节点的时候,都把该节点直接旋转到根
核心操作:splay(x) (把 x 节点旋转成根)

时间复杂度:均摊 $$\Theta(log_2N)$$

误区

不要使用Treap的旋转方式来对Splay进行旋转,这不叫Splay,这叫Spaly,时间复杂度为$$\Theta(玄学)$$

我们把 Treap 的旋转称为单旋,接下来我们要学的另一种适用于Splay的旋转:双旋

旋转

有两种旋转方式。

一字型旋转适用于在同一子树时的情况,具体如图:

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Splay1.png 旋转为 https://blog.aor.sd.cn/wp-content/uploads/2018/11/Splay2.png


工字型旋转适用于两个结点不在同一子树里的时候,具体看图:

https://blog.aor.sd.cn/wp-content/uploads/2018/11/Splay3.png旋转为https://blog.aor.sd.cn/wp-content/uploads/2018/11/Splay4.png

过程

X 反复双旋,直到 X 为根或者根的儿子
如果 X 是根的儿子,则 X 单旋

如果 X 是根,过程结束

代码实现

普通平衡树为例

最后

掌握了模板才是学习的开始,尝试去独立切一些平衡树题目吧!Good Luck!

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/29
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

平衡树学习笔记
定义 什么叫平衡树?就是看起来很平衡的树。 它是一种中序遍历有序的一棵搜索树,满足左儿子的权值<自身权值<右儿子的权值 它是递归定义的。 算法 目前平衡树的算法很多,在…
扫描二维码继续阅读
2018-05-02
标签
近期评论