Splay平衡树 学习笔记

0 前言

突然想学$Link Cut Tree$了(当然不是因为我们班里有一个叫$LCT$的人
但是$LCT$有一个非常重要的前置知识,那就是$Splay$,于是就有了此篇文章。

1 Splay原理

BST

要想理解$splay$的原理,就得先理解$BST$。
二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。
比如这个就是一棵二叉查找树:

但是如果这棵二叉树变得丑陋点,就成了这样:

于是最坏查询情况就变成了$O(N)$这就尴尬了。

Splay

那么怎么解决如上所示的问题呢?
于是就变成了各种树。
其中有一位大佬叫$Tarjan$(怎么又是他
发明了$Splay$
那么$Splay$是怎么解决这个问题的呢?
$Tarjan$想出了旋转。

2 Splay详解

Rotate

如图,我们有一棵二叉树,$X,Y,Z$分别代表三个节点,$A,B,C$分别代表三个子树。

现在,我们要把这棵二叉树的$X$节点转到$Y$节点的位置。
因为$X$是$Y$的左儿子,所以$X<Y$,所以旋转后$Y$必定是$X$的右儿子。
因为$Y$是$Z$的左儿子,所以$Y<Z$。
所以$X<Z$,所以如果把$X转到Y$,旋转后$X$必定是$Z$的左儿子。
因为$X$的子树及$X$本身构成了$Y$的左儿子,所以$X$的子树及$X$本身一定$<Y$。
所以$X<B<Y$,所以$B$旋转后是$Y$的左儿子。
因为$C$是$Y$的右儿子,所以$C>Y$,旋转后$C$一定是$Y$的右儿子。
而$X$的左儿子$A$是最小的,所以不管他,旋转后$A$还是$X$的左儿子。
检查一遍:$A<X<B<Y<C<Z$没有问题。
现在虽然树的形态变了,但是它还是一棵平衡树,并且好像更好看了(雾
自己再画画看,总共有$4$种情况。

图画完了,我们可以总结下规律了。

  1. $X$旋转后到$Y$的位置。
  2. $Y$旋转后到$X$原来在$Y$的那个儿子的相对的儿子(如果$X$原来是$Y$的左儿子,$Y$旋转后就是$X$的右儿子)。
  3. $Y$的另一个不是$X$的儿子不变,$X$的原来$X$在$Y$的方向的儿子不变(如果$X$原来是$Y$的左儿子,$X$的左儿子就不变,$Y$的右儿子不变)。
  4. $X$的原来$X$在$Y$的方向相对的儿子旋转后变成了原来$X$在$Y$方向上的$Y$的儿子(如果$X$原来是$Y$的左儿子,$X$的右儿子就变成了$Y$的左儿子)。

Splay

接下来考虑下一个问题:怎样把一个节点旋转到根节点呢?(比如上文的$X$旋转到$Z$)
先把$X$转到$Y$,再把$Y$转到$Z$?显然这是不行的,可以自己动手画一画,在某些情况下某条链可能仍然存在,这种情况下,$Splay$极有可能会被卡。
图我就不画了(懒
总结在这:

  1. $X$和$Y$分别是$Y$和$Z$的同一个儿子(如$X$是$Y$的左儿子,$Y$是$Z$的左儿子),先旋转$Y$,再旋转$X$。
  2. $X$和$Y$分别是$Y$和$Z$的不同儿子(如$X$是$Y$的左儿子,$Y$是$Z$的右儿子),对$X$旋转$2$次。

剩下的操作

剩下的操作和普通的$BST$差不多,这里就不再介绍。

3 Splay Code

Luogu P3369 【模板】普通平衡树

评论

  1. vibrant72
    Windows Chrome 78.0.3904.108
    4月前
    2020-8-13 14:58:28

    orz

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇