Splay 树

本页面将简要介绍如何用 Splay 维护二叉查找树。

定义

Splay 树, 或 伸展树，是一种平衡二叉查找树，它通过 Splay/伸展操作 不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，能够在均摊 时间内完成插入，查找和删除操作，并且保持平衡而不至于退化为链。

Splay 树由 Daniel Sleator 和 Robert Tarjan 于 1985 年发明。

结构

二叉查找树的性质

首先肯定是一棵二叉树！

能够在这棵树上查找某个值的性质：左子树任意节点的值 根节点的值 右子树任意节点的值。

节点维护信息

rt	tot	fa[i]	ch[i][0/1]	val[i]	cnt[i]	sz[i]
根节点编号	节点个数	父亲	左右儿子编号	节点权值	权值出现次数	子树大小

操作

基本操作

• maintain(x)：在改变节点位置后，将节点 的 更新。
• get(x)：判断节点 是父亲节点的左儿子还是右儿子。
• clear(x)：销毁节点 。

旋转操作

为了使 Splay 保持平衡而进行旋转操作，旋转的本质是将某个节点上移一个位置。

旋转需要保证：

• 整棵 Splay 的中序遍历不变（不能破坏二叉查找树的性质）。
• 受影响的节点维护的信息依然正确有效。
• root 必须指向旋转后的根节点。

在 Splay 中旋转分为两种：左旋和右旋。

过程

具体分析旋转步骤（假设需要旋转的节点为 ，其父亲为 ，以右旋为例）

1. 将 的左儿子指向 的右儿子，且 的右儿子（如果 有右儿子的话）的父亲指向 ；ch[y][0]=ch[x][1]; fa[ch[x][1]]=y;
2. 将 的右儿子指向 ，且 的父亲指向 ；ch[x][chk^1]=y; fa[y]=x;
3. 如果原来的 还有父亲 ，那么把 的某个儿子（原来 所在的儿子位置）指向 ，且 的父亲指向 。fa[x]=z; if(z) ch[z][y==ch[z][1]]=x;

实现

Splay 操作

Splay 操作规定：每访问一个节点 后都要强制将其旋转到根节点。

Splay 操作即对 做一系列的 splay 步骤。每次对 做一次 splay 步骤， 到根节点的距离都会更近。定义 为 的父节点。Splay 步骤有三种，具体分为六种情况：

1. zig: 在 是根节点时操作。Splay 树会根据 和 间的边旋转。 存在是用于处理奇偶校验问题，仅当 在 splay 操作开始时具有奇数深度时作为 splay 操作的最后一步执行。

   

   即直接将 左旋或右旋（图 1, 2）

   

   

2. zig-zig: 在 不是根节点且 和 都是右侧子节点或都是左侧子节点时操作。下方例图显示了 和 都是左侧子节点时的情况。Splay 树首先按照连接 与其父节点 边旋转，然后按照连接 和 的边旋转。

   

   即首先将 左旋或右旋，然后将 右旋或左旋（图 3, 4）。

   

   

3. zig-zag: 在 不是根节点且 和 一个是右侧子节点一个是左侧子节点时操作。Splay 树首先按 和 之间的边旋转，然后按 和 新生成的结果边旋转。

   

   即将 先左旋再右旋、或先右旋再左旋（图 5, 6）。

   

   

   tip

   请读者尝试自行模拟 种旋转情况，以理解 Splay 的基本思想。

实现

Splay 操作的时间复杂度

因为 zig 和 zag 是 对称 操作，我们只需要对 zig，zig−zig，zig−zag 操作分析复杂度。采用

势能分析，定义一个 个节点的 splay 树进行了 次 splay 步骤。可记 , 定义势能函数为 ,，在第 次操作后势能为 , 则我们只需要求出初始势能和每次的势能变化量的和即可。

1. zig: 势能的变化量为

2. zig-zig: 势能变化量为

3. zig-zag: 势能变化量为

由此可见，三种 splay 步骤的势能全部可以缩放为 . 令 ,, 假设 splay 操作一次依次访问了 , 最终 成为根节点，我们可以得到：

继而可得：

因此，对于 个节点的 splay 树，做一次 splay 操作的均摊复杂度为 。因此基于 splay 的插入，查询，删除等操作的时间复杂度也为均摊 。

插入操作

过程

插入操作是一个比较复杂的过程，具体步骤如下（假设插入的值为 ）：

• 如果树空了，则直接插入根并退出。
• 如果当前节点的权值等于 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
• 否则按照二叉查找树的性质向下找，找到空节点就插入即可（请不要忘记 Splay 操作）。

实现

查询 x 的排名

过程

根据二叉查找树的定义和性质，显然可以按照以下步骤查询 的排名：

• 如果 比当前节点的权值小，向其左子树查找。
• 如果 比当前节点的权值大，将答案加上左子树（）和当前节点（）的大小，向其右子树查找。
• 如果 与当前节点的权值相同，将答案加 并返回。

注意最后需要进行 Splay 操作。

实现

查询排名 x 的数

过程

设 为剩余排名，具体步骤如下：

• 如果左子树非空且剩余排名 不大于左子树的大小 ，那么向左子树查找。
• 否则将 减去左子树的和根的大小。如果此时 的值小于等于 ，则返回根节点的权值，否则继续向右子树查找。

实现

查询前驱

过程

前驱定义为小于 的最大的数，那么查询前驱可以转化为：将 插入（此时 已经在根的位置了），前驱即为 的左子树中最右边的节点，最后将 删除即可。

实现

查询后继

过程

后继定义为大于 的最小的数，查询方法和前驱类似： 的右子树中最左边的节点。

实现

合并两棵树

过程

合并两棵 Splay 树，设两棵树的根节点分别为 和 ，那么我们要求 树中的最大值小于 树中的最小值。合并操作如下：

• 如果 和 其中之一或两者都为空树，直接返回不为空的那一棵树的根节点或空树。
• 否则将 树中的最大值 到根，然后把它的右子树设置为 并更新节点的信息，然后返回这个节点。

删除操作

过程

删除操作也是一个比较复杂的操作，具体步骤如下：

首先将 旋转到根的位置。

• 如果 （有不止一个 ），那么将 减 并退出。
• 否则，合并它的左右两棵子树即可。

实现

实现

例题

以下题目都是裸的 Splay 维护二叉查找树。

• 【模板】普通平衡树
• 【模板】文艺平衡树
• 「HNOI2002」营业额统计
• 「HNOI2004」宠物收养所

习题

• 「Cerc2007」robotic sort 机械排序
• 二逼平衡树（树套树）
• bzoj 2827 千山鸟飞绝
• 「Lydsy1706 月赛」K 小值查询

参考资料与注释

本文部分内容引用于 algocode 算法博客，特别鸣谢！