Tree
本文目录
一、伸展树的基本概念
二、Splay —— 伸展操作的原理
1、P 是根节点
2、P 不是根节点
Z字型旋转（Zig-zag）
一字型旋转（Zig-zig）—— 左
一字型旋转（Zig-zig）—— 右
三、伸展操作的实现
四、利用伸展树实现其他操作
1、Find(x,S)
2、Insert(x,S)
3、Delete(x,S)
4、Join(S1,S2)
5、Split(x,S)
本文将要介绍的伸展树（Splay Tree），是对二叉查找树的一种改进。
虽然它并不能保证树的外观结构上一直是“平衡”的，但对于伸展树的一系列操作，我们可以证明其每一步操作的平摊复杂度都是O(log n)。所以从性能上说，伸展树也是一种平衡的二叉查找树。而在各种树状数据结构中，伸展树的空间要求与编程复杂度也都是很优秀的。
一、伸展树的基本概念
伸展树是二叉查找树的一种改进，与二叉查找树一样，伸展树也具有有序性 —— 对于每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。
比二叉查找树更丰富的是：伸展树可以自我调整 —— 展开（splay）操作：可以将某一元素x所在节点调整到根部。
为了方便理解，下面对任意一非根节点x给出以下定义：
父亲节点P：x的父节点
祖父节点G：P的父节点
二、Splay —— 伸展操作的原理
伸展操作：在保持伸展树有序性的前提下，通过一系列旋转操作将伸展树中的元素x调整至树的根部。
对于旋转的操作，如果没有接触过的话，建议先看看AVL树的旋转（传送门->秒懂AVL树）
且以下旋转操作不要与AVL树旋转混淆，有所异同。
1、P 是根节点
直接将x与p单即可旋转，如果x是P的左孩子就进行左旋转，反之进行右旋转。
和AVL树的单旋转一样
2、P 不是根节点
Z字型旋转（Zig-zag）
一般模型如下图：
适用情况：x、P、G路径构成折线。
注意理解：上面只是显示了从G开始的树，并不代表G就是根节点。从一般情况下理解：图中的树也许只是某一棵树的一部分子树。
具体步骤：与AVL树的单旋转还是有差别的
🔺 将X的右子树挂在G的左子树上（此时P与G断开了）
🔺 将X的左子树挂在P的右子树上（此时X与P断开了）
🔺 将G挂在X的右子树上
🔺 将P挂在X的左子树上
一字型旋转（Zig-zig）—— 左
适用情况：x、P、G路径是直线段，无折点。
注意理解：上面只是显示了从G开始的树，并不代表G就是根节点。从一般情况下理解：图中的树也许只是某一棵树的一部分子树。
具体步骤：与AVL树的单旋转还是有差别的
🔺 将P的右子树挂在G的左子树上（此时P与G断开了）
🔺 将G挂在P的右子树上
🔺 将X的右子树挂在P的左子树上（此时X与P断开了）
🔺 将P挂在X的右子树上
一字型旋转（Zig-zig）—— 右
和左的情况差不多，先省去不写了。
下面来个实际的例子理解一波：
将这棵树在K1处伸展（将K1移动到根节点）
▲先经过Z字型旋转：
▲再经过一字型旋转：
可以发现：其实伸展操作不仅仅将节点移动到了树的根部，其也将旋转路径上大多数节点的深度减半，让树更加均衡了。
三、伸展操作的实现
Splay(x,S)：将x转移到伸展树S的根节点上
代码实现如下：
四、利用伸展树实现其他操作
利用Splay操作，我们可以在伸展树上进行如下运算：
1、Find(x,S)
判断元素x是否在伸展树S表示的有序集中。
首先，与在二叉查找树中的查找操作一样，在伸展树中查找元素x。如果x在树中，则再执行Splay(x,S)调整伸展树。
2、Insert(x,S)
将元素x插入伸展树S表示的有序集中。
首先，也与处理普通的二叉查找树一样，将x 插入到伸展树S中的相应位置上，再执行Splay(x,S)。
3、Delete(x,S)
将元素x从伸展树S所表示的有序集中删除。
首先，用在二叉查找树中查找元素的方法找到x的位置。如果x没有孩子或只有一个孩子，那么直接将x删去，并通过Splay操作，将x节点的父节点调到伸展树的根节点处。否则，则向下查找x的后继y，用y替代x的位置，最后执行Splay(y,S)，将y调整为伸展树的根。
4、Join(S1,S2)
将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素。首先，我们找到伸展树S1 中最大的一个元素x，再通过Splay(x,S1)将x 调整到伸展树S1 的根。然后再将S2 作为x 节点的右子树。这样，就得到了新的伸展树S。
5、Split(x,S)
以x 为界，将伸展树S 分离为两棵伸展树S1 和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。首先执行Find(x,S)，将元素x 调整为伸展树的根节点，则x 的左子树就是S1，而右子树为S2。
End
欢迎关注个人公众号“鸡翅编程”，这里是认真且乖巧的码农一枚，旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~