Splay学习笔记1——单点修改与基本操作

前言

关于Splay的学习笔记有三篇，这是其中的第一篇，三篇的内容分别为——Splay的单点修改与基本操作、区间操作，扩展：LCT（动态树）。

前置知识——二叉搜索树（BST）

定义；二叉搜索树（Binary Search Tree，简称BST），也被称为二叉排序树或二叉查找树，是一种特殊的二叉树。它的特点是：任意节点的左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

根据它的定义我们可以推知：二叉搜索树的中序遍历的结果是一个有序数列。

以上的特性使得二叉搜索树支持高效的数据搜索、插入和删除操作，我们可以用它来进行数列的维护，包括插入与删除某个数，以及快速查询数列中某个数的一些性质，比如它在数列中的排位，小于它的数的数量等，而这些具体的操作在后续将要讲的 Splay 的基本操作中会详细讲解。

BST 的限制

虽然 BST 有着很好的性质与强大的功能，但是它的性能是取决于树高的，所以当树退化成链时，它的单次查询与修改操作就会退化为 $O(n)$，性能损失极大，于是我们引入了一种新的数据结构——平衡树来解决这个问题。

什么是平衡树

根据上文的分析，BST 的主要问题是当树高很大时，时间损耗也会随之变大，于是，一个很自然的想法，我们只需要使树高保持一个较低的水平，那么就可以使 BST 的复杂度降下来了，而平衡树正是不断做这样的事的一种“升级版BST”。

平衡树的种类很多，有 Treap、FHQ-Treap、红黑树、替罪羊树等，而这篇学习笔记讲的是一种应用广泛但难度较大的平衡树——Splay 树。

Splay 的优缺点

在正式学习之前，先介绍一下 Splay 树的优缺点，以便做题时合理选择算法。

Splay 是一种优缺点非常鲜明的平衡树。它的优点是操作灵活，支持单点修改与区间操作，功能全面，最重要的一点是：它是 LCT 算法的核心基础，不可替代；而缺点是学习难度大，码量大，常数较大，不支持可持久化。

Splay 的节点结构

Splay 的基本结构定义如下：

struct BST{
    int fa,l,r,cnt,val,sz;
}tr[N];

其中，$fa$ 表示当前节点的父亲，$l$、$r$ 分别代表当前节点的左儿子与右儿子，$val$ 表示当前节点的关键字（即代表的数值），$sz$ 表示当前节点的子树大小，而 $cnt$ 是在当前维护的数列可重集（即有重复的数值）时会用到，表示当前节点的关键字出现了几次。

Splay 的基本流程

Splay 的核心优化是在每一次查询与操作时，都将当前查询或操作的点移到根的位置。除此之外，其他操作与 BST 的操作几乎一致。

旋转

Splay 将节点移到根的操作基础就是旋转，由于 BST 维护的是一棵中序遍历结果是有序数列的树，所以只要我们如果能够维护一棵树，使其中序遍历的结果与原本的 BST 相同，那么两棵树就是等价的，而 Splay 中的“旋转”，就是对树做的一种等价变换，使当前的节点变换到上一层去，具体来说，Splay 中的“旋转”分为以下两种：

1. 左旋

若当前要旋转的节点为其父亲的右儿子，此时将其变换到上一层的操作被称为“左旋”。

如图，当 $y$ 为 $x$ 的右儿子，$A$ 为 $x$ 左子树，$B$ 为 $y$ 左子树，$C$ 为 $y$ 右子树时：

我们希望将 $y$ 变换到 $x$ 的位置上，将 $x$ 变换下去，按照定义中的大小关系， $x$ 比 $y$ 小，所以应将 $x$ 设为 $y$ 的左子树，而 $x$ 的左子树 $A$ 的顶点比 $x$ 还小，所以应该让 $A$ 继续为 $x$ 的左子树，而 $y$ 的左子树 $B$ 的顶点比 $y$ 小，应该处在 $y$ 的左子树中，而根据定义， $B$ 的顶点比 $x$ 大，所以 $B$ 可以在 $x$ 的右子树位置上，$y$ 的右子树 $C$ 的顶点比 $y$ 大，可以继续处在 $y$ 的右子树上，这样，我们发现 $x$ 的子树部分依然是合法且成立的，而 $x$ 与 $y$ 都位于 $x$ 父亲的同一分支子树下，即它们与 $x$ 的父亲的大小关系是一样的，所以这一整块的子树在整棵树中的也是在合法位置上，整棵树依然是成立的，所以我们的“等价变换”（即“旋转”）就完成了，变换后的结构如下：