Splay 树
本页面将简要介绍如何用 Splay 维护二叉查找树。
定义
Splay 树,或 伸展树,是一种平衡二叉查找树,它通过 伸展(splay)操作 不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找树的性质,能够在均摊
Splay 树由 Daniel Sleator 和 Robert Tarjan 于 1985 年发明。
基本结构与操作
本节讨论 Splay 树的基本结构和它的核心操作,其中最为重要的是伸展操作。
Splay 树是一棵二叉查找树,查找某个值时满足性质:左子树任意节点的值
维护信息
本文使用数组模拟指针来实现 Splay 树,需要维护如下信息:
rt | id | fa[i] | ch[i][0/1] | val[i] | cnt[i] | sz[i] |
---|---|---|---|---|---|---|
根节点编号 | 已使用节点个数 | 父亲 | 左右儿子编号 | 节点权值 | 权值出现次数 | 子树大小 |
初始化时,所有信息都置零即可。
辅助操作
首先是一些简单的辅助操作:
dir(x)
:判断节点是父亲节点的左儿子还是右儿子; push_up(x)
:在改变节点位置后,根据子节点信息更新节点的信息。
实现
旋转操作
为了使 Splay 保持平衡,需要进行旋转操作。旋转的作用是将某个节点上移一个位置。
旋转需要保证:
- 整棵 Splay 的中序遍历不变(不能破坏二叉查找树的性质);
- 受影响的节点维护的信息依然正确有效;
rt
必须指向旋转后的根节点。
在 Splay 中旋转分为两种:左旋和右旋。
观察图示可知,如果要通过旋转将节点
具体分析旋转步骤:(假设需要上移的节点为
- 首先,记录节点
的父节点 ,以及 的父节点 (可能为空),并记录 是 的左子节点还是右子节点; - 按照旋转后的树中自下向上的顺序,依次更新
的左子节点为 的右子节点, 的右子节点为 ,以及若 非空, 的子节点为 ; - 按照同样的顺序,依次更新当前
的左子节点(若存在)的父节点为 , 的父节点为 ,以及 的父节点为 ; - 自下而上维护节点信息。
实现
在所有函数的实现时,都应注意不要修改节点
伸展操作
Splay 树要求每访问一个节点
设刚访问的节点为
-
zig: 在
是根节点时操作。Splay 树会根据 和 间的边旋转。zig 存在是用于处理奇偶校验问题,仅当 在伸展操作开始时具有奇数深度时作为伸展操作的最后一步执行。 即直接将
右旋或左旋(图 1, 2)。 -
zig-zig: 在
不是根节点且 和 都是右侧子节点或都是左侧子节点时操作。下方例图显示了 和 都是左侧子节点时的情况。Splay 树首先按照连接 与其父节点 边旋转,然后按照连接 和 的边旋转。 即首先将
右旋或左旋,然后将 右旋或左旋(图 3, 4)。 -
zig-zag: 在
不是根节点且 和 一个是右侧子节点一个是左侧子节点时操作。Splay 树首先按 和 之间的边旋转,然后按 和 新生成的结果边旋转。 即将
先左旋再右旋或先右旋再左旋(图 5, 6)。
Tip
请读者尝试自行模拟
比较三种伸展步骤可知,要区分此时应使用哪种操作,关键是要判断
此处提供的实现,可以指定任意根节点
- 首先记录根节点
的父节点 ,从而可以利用 fa[x] == w
判断已经位于根结点处; - 记录
当前的父节点 ,如果 和 相同,说明 已经到达根节点; - 否则,利用
fa[y] == w
判断是否是根节点。如果是,直接做 zig 操作将 旋转;如果不是,利用 dir(x) == dir(y)
判断使用 zig-zig 还是 zig-zag,前者先旋转再旋转 ,后者直接旋转两次 。
实现
伸展操作是 Splay 树的核心操作,也是它的时间复杂度能够得到保证的关键步骤。请务必保证每次向下访问节点后,都进行一次伸展操作。
另外,伸展操作会将当前节点
时间复杂度
对大小为
基于势能分析的复杂度证明
为此只需分析 zig、zig-zig 和 zig-zag 三种操作的复杂度。为此,我们采用 势能分析法,通过研究势能的变化来推导操作的均摊复杂度。假设对一棵包含
定义:
-
单个节点的势能:
,其中 表示以节点 为根的子树大小。 -
整棵树的势能:
,即树中所有节点势能的总和,初始势能满足 。 -
第
次操作的均摊成本: ,其中 为实际操作代价, 和 分别为操作后和操作前的势能。
性质:
- 如果
是 的父节点,则有 ,即父节点的势能不小于子节点的势能。 - 由于根节点的子树大小在操作前后保持不变,因此根节点的势能在操作过程中不变。
- 如果
,那么有 。
性质 3 的证明
根据均值不等式可知
接下来,分别对 zig、zig-zig 和 zig-zag 操作进行势能分析。设操作前后的节点
zig:根据性质 1 和 2,有
zig-zig:根据性质 1 和 2,有
根据性质 3 可得
由此,均摊成本为
zig-zag:根据性质 1 和 2,有
由此,均摊成本为
单次伸展操作:
令
因此,一次伸展操作的均摊复杂度是
结论:
在进行
因此,
为什么 Splay 树的再平衡操作可以获得 的均摊复杂度?
朴素的再平衡思路就是对节点反复进行旋转操作使其上升,直到它成为根节点。这种朴素思路的问题在于,对于所有子节点都是左(右)节点的链状树来说,它相当于反复进行 zig 操作,因而 zig 操作的均摊复杂度中的常数项
平衡树操作
本节讨论基于 Splay 树实现平衡树的常见操作的方法。其中,较为重要的是按照值或排名查找元素,它们可以将某个特定的元素找到,并上移至根节点处,以便后续处理。
作为例子,本节将讨论模板题目 普通平衡树 的实现。
按照值查找
作为二叉查找树,可以通过值
应注意,经常存在树中不存在相应的节点的情形。对于这种情形,要记录最后一个访问的节点(即实现中的
实现
该实现允许指定任何节点
按照排名访问
因为记录了子树大小信息,所以 Splay 树还可以通过排名访问元素,即查找树中第
设
- 如果左子树非空且剩余排名
不大于左子树的大小,那么向左子树查找; - 否则,如果
不大于左子树加上根的大小,那么根节点就是要寻找的; - 否则,将
减去左子树的和根的大小,继续向右子树查找; - 将最终找到的元素上移至根部。
实现
该实现需要保证排名
模板题目中操作
合并操作
有些时候需要合并两棵 Splay 树。
设两棵树的根节点分别为
合并操作如下:
- 如果
和 其中之一或两者都为空树,直接返回不为空的那一棵树的根节点或空树; - 否则,通过
loc(y, 1)
将树中的最小值上移至根 处,再将它的左节点(此时必然为空)设置为 ,并更新节点信息,返回节点 。
实现
分裂操作类似。因而,Splay 树可以模拟 无旋 treap 的思路做各种操作,包括区间操作。后文 会介绍更具有 Splay 树风格的区间操作处理方法。
插入操作
插入操作是一个比较复杂的过程。具体步骤如下:(假设插入的值为
- 类似按值查找的过程,根据
向下查找到存储 的节点或者空节点,过程中记录父节点 ; - 如果存在存储
的节点 ,直接更新信息,否则就新建节点 ; - 做伸展操作,将最后一个节点
上移至根部。
实现
该实现允许直接向空树内插入值。若不想处理空树,可以在树中提前插入哑节点。
删除操作
删除操作也是一个比较复杂的操作。具体步骤如下:(假设删除的值为
- 首先按照值
查找存储它的节点,并上移至根部; - 如果不存在存储它的节点,直接返回;(上一步已经做了伸展操作)
- 否则,更新节点信息;
- 如果得到的根节点为空节点,就合并左右子树作为新的根节点,注意合并前需要更新两个子树的根的父节点为空。
实现
查询排名
直接按照值
注意,当 find(rt, v)
返回的根和
查询前驱
前驱定义为小于
- 按照值
访问节点(并上移至根部); - 如果根部的值小于
,那么它必然是最大的那个,直接返回; - 否则,在左子树中找到最大值,并上移至根部。
最后一步相当于直接调用 loc(ch[rt][0], cnt[ch[rt][0]])
,只是省去了不必要的判断。
实现
该实现允许前驱不存在,此时返回
查询后继
后继定义为大于 loc(ch[rt][1], 1)
。
实现
参考实现
本节的最后,给出模板题目 普通平衡树 的参考实现。
参考实现
#include <iostream>
constexpr int N = 2e6;
int id, rt;
int fa[N], val[N], cnt[N], sz[N], ch[N][2];
bool dir(int x) { return x == ch[fa[x]][1]; }
void push_up(int x) { sz[x] = cnt[x] + sz[ch[x][0]] + sz[ch[x][1]]; }
void rotate(int x) {
int y = fa[x], z = fa[y];
bool r = dir(x);
ch[y][r] = ch[x][!r];
ch[x][!r] = y;
if (z) ch[z][dir(y)] = x;
if (ch[y][r]) fa[ch[y][r]] = y;
fa[y] = x;
fa[x] = z;
push_up(y);
push_up(x);
}
void splay(int& z, int x) {
int w = fa[z];
for (int y; (y = fa[x]) != w; rotate(x)) {
if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
}
z = x;
}
void find(int& z, int v) {
int x = z, y = fa[x];
for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
splay(z, x ? x : y);
}
void loc(int& z, int k) {
int x = z;
for (;;) {
if (sz[ch[x][0]] >= k) {
x = ch[x][0];
} else if (sz[ch[x][0]] + cnt[x] >= k) {
break;
} else {
k -= sz[ch[x][0]] + cnt[x];
x = ch[x][1];
}
}
splay(z, x);
}
int merge(int x, int y) {
if (!x || !y) return x | y;
loc(y, 1);
ch[y][0] = x;
fa[x] = y;
push_up(y);
return y;
}
void insert(int v) {
int x = rt, y = 0;
for (; x && val[x] != v; x = ch[y = x][v > val[x]]);
if (x) {
++cnt[x];
++sz[x];
} else {
x = ++id;
val[x] = v;
cnt[x] = sz[x] = 1;
fa[x] = y;
if (y) ch[y][v > val[y]] = x;
}
splay(rt, x);
}
bool remove(int v) {
find(rt, v);
if (!rt || val[rt] != v) return false;
--cnt[rt];
--sz[rt];
if (!cnt[rt]) {
int x = ch[rt][0];
int y = ch[rt][1];
fa[x] = fa[y] = 0;
rt = merge(x, y);
}
return true;
}
int find_rank(int v) {
find(rt, v);
return sz[ch[rt][0]] + (val[rt] < v ? cnt[rt] : 0) + 1;
}
int find_kth(int k) {
if (k > sz[rt]) return -1;
loc(rt, k);
return val[rt];
}
int find_prev(int v) {
find(rt, v);
if (rt && val[rt] < v) return val[rt];
int x = ch[rt][0];
if (!x) return -1;
for (; ch[x][1]; x = ch[x][1]);
splay(rt, x);
return val[rt];
}
int find_next(int v) {
find(rt, v);
if (rt && val[rt] > v) return val[rt];
int x = ch[rt][1];
if (!x) return -1;
for (; ch[x][0]; x = ch[x][0]);
splay(rt, x);
return val[rt];
}
int main() {
int n;
std::cin >> n;
for (; n; --n) {
int op, x;
std::cin >> op >> x;
switch (op) {
case 1:
insert(x);
break;
case 2:
remove(x);
break;
case 3:
std::cout << find_rank(x) << '\n';
break;
case 4:
std::cout << find_kth(x) << '\n';
break;
case 5:
std::cout << find_prev(x) << '\n';
break;
case 6:
std::cout << find_next(x) << '\n';
break;
}
}
return 0;
}
序列操作
Splay 树也可以运用在序列上,用于维护区间信息。与线段树对比,Splay 树常数较大,但是支持更复杂的序列操作,如区间翻转等。上文提到 Splay 树同样支持分裂和合并操作,因而可以模拟 无旋 treap 进行区间操作,在此不再过多讨论。本节主要讨论基于伸展操作的区间操作实现方法。
将序列建成的 Splay 树有如下性质:
- Splay 树的中序遍历相当于原序列从左到右的遍历;
- Splay 树上的一个节点代表原序列的一个元素;
- Splay 树上的一颗子树,代表原序列的一段区间。
因为有伸展操作,可以快速提取出代表某个区间的 Splay 子树。
作为例子,本节将讨论模板题目 文艺平衡树 的实现。
根据序列建树
在操作之前,需要根据所给的序列先把 Splay 树建出来。根据 Splay 树的特性,直接建出一颗只有左儿子的链即可。时间复杂度是
参考实现
最后的伸展操作自下而上地更新了节点信息。为了后文区间操作方便,序列左右两侧添加了两个哨兵节点。
区间翻转
以区间翻转为例,可以理解区间操作的方法:(设区间为
- 首先将节点
上移到根节点,再在其右子树中,将节点 上移到右子树的根节点; - 此时,设
为根节点的右子节点的左子节点,则以 为根的子树就对应着区间 ; - 在
处对区间 做操作,并打上懒标记; - 在
处将标记下传一次,然后利用伸展操作将 上移到根。
第一步需要的操作就是前文平衡树操作中的「按照排名访问」,因为元素的标号就是它的排名。因为涉及懒标记的管理,它的实现与上文略有不同。
参考实现
最后一步的伸展操作并非为了保证复杂度正确,而是为了更新节点信息。因为伸展操作涉及到节点
懒标记管理
首先,需要辅助函数 lazy_reverse(x)
和 push_down(x)
。前者交换左右节点,并更新懒标记;后者将标记下传。
参考实现
然后,只需要在向下经过节点时下传标记即可。模板题要求的操作比较简单,只有按照排名寻找的操作(即 loc
)涉及向下访问节点。注意,需要在函数每次访问一个新的节点 前 下传标记。
参考实现
因为向下访问节点时已经移除了经过的路径的所有懒标记,所以利用伸展操作上移节点时不再需要处理懒标记。但是,对于区间操作的那一个节点要谨慎处理:因为它同样位于伸展操作的路径上,但是刚刚操作完,可能存在尚未下传的标记,需要首先下传再做伸展操作,正如同上文所做的那样。
参考实现
本节的最后,给出模板题目 文艺平衡树 的参考实现。
参考实现
#include <iostream>
constexpr int N = 2e6;
int id, rt;
int fa[N], val[N], sz[N], lz[N], ch[N][2];
bool dir(int x) { return x == ch[fa[x]][1]; }
void push_up(int x) { sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]]; }
void lazy_reverse(int x) {
std::swap(ch[x][0], ch[x][1]);
lz[x] ^= 1;
}
void push_down(int x) {
if (lz[x]) {
if (ch[x][0]) lazy_reverse(ch[x][0]);
if (ch[x][1]) lazy_reverse(ch[x][1]);
lz[x] = 0;
}
}
void rotate(int x) {
int y = fa[x], z = fa[y];
bool r = dir(x);
ch[y][r] = ch[x][!r];
ch[x][!r] = y;
if (z) ch[z][dir(y)] = x;
if (ch[y][r]) fa[ch[y][r]] = y;
fa[y] = x;
fa[x] = z;
push_up(y);
push_up(x);
}
void splay(int& z, int x) {
int w = fa[z];
for (int y; (y = fa[x]) != w; rotate(x)) {
if (fa[y] != w) rotate(dir(x) == dir(y) ? y : x);
}
z = x;
}
void loc(int& z, int k) {
int x = z;
for (push_down(x); sz[ch[x][0]] != k - 1; push_down(x)) {
if (sz[ch[x][0]] >= k) {
x = ch[x][0];
} else {
k -= sz[ch[x][0]] + 1;
x = ch[x][1];
}
}
splay(z, x);
}
void build(int n) {
for (int i = 1; i <= n + 2; ++i) {
++id;
ch[id][0] = rt;
if (rt) fa[rt] = id;
rt = id;
val[id] = i - 1;
}
splay(rt, 1);
}
void reverse(int l, int r) {
loc(rt, l);
loc(ch[rt][1], r - l + 2);
int x = ch[ch[rt][1]][0];
lazy_reverse(x);
push_down(x);
splay(rt, x);
}
void print(int x) {
if (!x) return;
push_down(x);
print(ch[x][0]);
std::cout << val[x] << ' ';
print(ch[x][1]);
}
void print() {
loc(rt, 1);
loc(ch[rt][1], sz[rt] - 1);
print(ch[ch[rt][1]][0]);
}
int main() {
int n, m;
std::cin >> n >> m;
build(n);
for (; m; --m) {
int l, r;
std::cin >> l >> r;
reverse(l, r);
}
print();
return 0;
}
习题
这些题目都是裸的 Splay 树维护二叉查找树:
Splay 树还出现在更复杂的应用场景中:
- 「Cerc2007」robotic sort 机械排序
- 「HNOI2011」括号修复/「JSOI2011」括号序列
- 二逼平衡树(树套树)
- BZOJ 2827 千山鸟飞绝
- 「Lydsy1706 月赛」K 小值查询
- POJ3580 SuperMemo
参考资料与注释
本文部分内容引用于 algocode 算法博客,特别鸣谢!
创建日期: 2018年7月11日