学习笔记：Splay

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

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

结构
节点维护信息
x tot fa[i] ch[i][0/1] val[i] cnt[i] sz[i]
根节点编号 节点个数 父亲 左右儿子编号 节点权值 权值出现次数 子树大小
struct Splay{
int fa, ch[2], val, cnt, siz;
}tree[MAXN];
操作
基本操作
maintain(x)：在改变节点位置后，将节点 $x$ 的 $\text{size}$ 更新。
get(x)：判断节点 $x$ 是父亲节点的左儿子还是右儿子。
clear(x)：销毁节点 $x$。
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
if(x == tree[tree[x].fa].ch[1])return true;
else return false;
}
void clear(int x){
tree[tree[x].ch[0]].siz = 0;
tree[tree[x].ch[1]].siz = 0;
tree[x].fa = 0;tree[x].val = 0;
tree[x].cnt = 0;tree[x].siz = 0;
}
旋转操作
为了使 Splay 保持平衡而进行旋转操作，旋转的本质是将某个节点上移一个位置。

旋转需要保证：

整棵 Splay 的中序遍历不变(不能破坏二叉查找树的性质)。
受影响的节点维护的信息依然正确有效。
root 必须指向旋转后的根节点。
在 Splay 中旋转分为两种：左旋和右旋。

过程
具体分析旋转步骤(假设需要旋转的节点为 $x$，其父亲为 $y$，以右旋为例)

将 $y$ 的左儿子指向 $x$ 的右儿子，且 $x$ 的右儿子(如果 $x$ 有右儿子的话)的父亲指向 $y$；ch[y][0] = ch[x][1];fa[ch[x][1]] = y;
将 $x$ 的右儿子指向 $y$，且 $y$ 的父亲指向 $x$；ch[x][chk^1] = y;fa[y] = x;
如果原来的 $y$ 还有父亲 $z$，那么把 $z$ 的某个儿子(原来 $y$ 所在的儿子位置)指向 $x$，且 $x$ 的父亲指向 $z$。fa[x] = z;if(z)ch[z][y == ch[z][1]] = x;
实现
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
Splay 操作
Splay 操作规定：每访问一个节点 $x$ 后都要强制将其旋转到根节点。

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

实现
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
插入操作
过程
插入操作是一个比较复杂的过程，具体步骤如下(假设插入的值为 $k$)：

如果树空了，则直接插入根并退出。
如果当前节点的权值等于 $k$ 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
否则按照二叉查找树的性质向下找，找到空节点就插入即可(请不要忘记 Splay 操作)。
实现
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
void insert(int k){
if(!root){
tree[++tot].val = k;tree[tot].cnt++;
root = tot;maintain(root);return;
}
int cur = root, f = 0;
while(true){
if(tree[cur].val == k){
tree[cur].cnt++;
maintain(cur);maintain(f);
splay(cur);break;
}
f = cur;cur = tree[f].ch[tree[f].val < k];
if(!cur){
tree[++tot].val = k;tree[tot].cnt++;tree[tot].fa = f;
tree[f].ch[tree[f].val < k] = tot;
maintain(tot);maintain(f);splay(tot);break;
}
}
}
查询 x 的排名
过程
根据二叉查找树的定义和性质，显然可以按照以下步骤查询 $x$ 的排名：

如果 $x$ 比当前节点的权值小，向其左子树查找。
如果 $x$ 比当前节点的权值大，将答案加上左子树($size$)和当前节点($cnt$)的大小，向其右子树查找。
如果 $x$ 与当前节点的权值相同，将答案加 $1$ 并返回。
注意最后需要进行 Splay 操作。

实现
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
int getrank(int k){
int res = 0, cur = root;
while(true){
if(k < tree[cur].val)cur = tree[cur].ch[0];
else{
res += tree[tree[cur].ch[0]].siz;
if(k == tree[cur].val){splay(cur);return res + 1;}
res += tree[cur].cnt;cur = tree[cur].ch[1];
}
}
}
查询排名 x 的数
过程
设 $k$ 为剩余排名，具体步骤如下：

如果左子树非空且剩余排名 $k$ 不大于左子树的大小 $size$，那么向左子树查找。
否则将 $k$ 减去左子树的和根的大小。如果此时 $k$ 的值小于等于 $0$，则返回根节点的权值，否则继续向右子树查找。
实现
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
int getval(int k){
int cur = root;
while(true){
if(tree[cur].ch[0] && k <= tree[tree[cur].ch[0]].siz)cur = tree[cur].ch[0];
else{k -= tree[tree[cur].ch[0]].siz + tree[cur].cnt;
if(k <= 0){splay(cur);return tree[cur].val;}
cur = tree[cur].ch[1];
}
}
}
查询前驱
过程
前驱定义为小于 $x$ 的最大的数，那么查询前驱可以转化为：将 $x$ 插入(此时 $x$ 已经在根的位置了)，前驱即为 $x$ 的左子树中最右边的节点，最后将 $x$ 删除即可。

实现
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
int getpre(){
int cur = tree[root].ch[0];
if(!cur)return cur;
while(tree[cur].ch[1])cur = tree[cur].ch[1];
splay(cur);return cur;
}
查询后继
过程
后继定义为大于 $x$ 的最小的数，查询方法和前驱类似：$x$ 的右子树中最左边的节点。

实现
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
int getnxt(){
int cur = tree[root].ch[1];
if(!cur)return cur;
while(tree[cur].ch[0])cur = tree[cur].ch[0];
splay(cur);return cur;
}
合并两棵树
过程
合并两棵 Splay 树，设两棵树的根节点分别为 $x$ 和 $y$，那么我们要求 $x$ 树中的最大值小于 $y$ 树中的最小值。合并操作如下：

如果 $x$ 和 $y$ 其中之一或两者都为空树，直接返回不为空的那一棵树的根节点或空树。
否则将 $x$ 树中的最大值 $\mathrm{Splay}$ 到根，然后把它的右子树设置为 $y$ 并更新节点的信息，然后返回这个节点。
删除操作
过程
删除操作也是一个比较复杂的操作，具体步骤如下：

首先将 $x$ 旋转到根的位置。

如果 $cnt[x]>1$(有不止一个 $x$)，那么将 $cnt[x]$ 减 $1$ 并退出。
否则，合并它的左右两棵子树即可。
实现
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void clear(int x){
tree[tree[x].ch[0]].siz = 0;
tree[tree[x].ch[1]].siz = 0;
tree[x].fa = 0;tree[x].val = 0;
tree[x].cnt = 0;tree[x].siz = 0;
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
int getrank(int k){
int res = 0, cur = root;
while(true){
if(k < tree[cur].val)cur = tree[cur].ch[0];
else{
res += tree[tree[cur].ch[0]].siz;
if(k == tree[cur].val){splay(cur);return res + 1;}
res += tree[cur].cnt;cur = tree[cur].ch[1];
}
}
}
int getpre(){
int cur = tree[root].ch[0];
if(!cur)return cur;
while(tree[cur].ch[1])cur = tree[cur].ch[1];
splay(cur);return cur;
}
void remove(int k){
getrank(k);
if(tree[root].cnt > 1){tree[root].cnt–;maintain(root);return;}
if(!tree[root].ch[0] && !tree[root].ch[1]){clear(root);root = 0;return;}
if(!tree[root].ch[0]){
int cur = root;root = tree[root].ch[1];
tree[root].fa = 0;clear(cur);return;
}
if(!tree[root].ch[1]){
int cur = root;root = tree[root].ch[0];
tree[root].fa = 0;clear(cur);return;
}
int cur = root, x = getpre();
tree[tree[cur].ch[1]].fa = root;
tree[root].ch[1] = tree[cur].ch[1];
clear(cur);maintain(root);
}
实现
#include
#define MAXN 100005
using namespace std;
int n, opt, x, root, tot;
struct splay{
int fa, ch[2], val, cnt, siz;
}tree[MAXN];
int read(){
int t = 1, x = 0;char ch = getchar();
while(!isdigit(ch)){if(ch == ‘-’)t = -1;ch = getchar();}
while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * t;
}
void write(int x){
if(x < 0){putchar(‘-’);x = -x;}
if(x >= 10)write(x/ 10);
putchar(x % 10 ^ 48);
}
void maintain(int x){
tree[x].siz = tree[tree[x].ch[0]].siz + tree[tree[x].ch[1]].siz + tree[x].cnt;
}
bool get(int x){
return x == tree[tree[x].fa].ch[1];
}
void clear(int x){
tree[tree[x].ch[0]].siz = 0;
tree[tree[x].ch[1]].siz = 0;
tree[x].fa = 0;tree[x].val = 0;
tree[x].cnt = 0;tree[x].siz = 0;
}
void rotate(int x){
int y = tree[x].fa, z = tree[y].fa, chk = get(x);
tree[y].ch[chk] = tree[x].ch[chk ^ 1];
if(tree[x].ch[chk ^ 1])tree[tree[x].ch[chk ^ 1]].fa = y;
tree[x].ch[chk ^ 1] = y;
tree[y].fa = x;tree[x].fa = z;
if(z != 0)tree[z].ch[y == tree[z].ch[1]] = x;
maintain(x);maintain(y);
}
void splay(int x){
for(int f = tree[x].fa ; f = tree[x].fa, f ; rotate(x))
if(tree[f].fa)rotate(get(x) == get(f) ? f : x);
root = x;
}
void insert(int k){
if(!root){
tree[++tot].val = k;tree[tot].cnt++;
root = tot;maintain(root);return;
}
int cur = root, f = 0;
while(true){
if(tree[cur].val == k){
tree[cur].cnt++;
maintain(cur);maintain(f);
splay(cur);break;
}
f = cur;cur = tree[f].ch[tree[f].val < k];
if(!cur){
tree[++tot].val = k;tree[tot].cnt++;tree[tot].fa = f;
tree[f].ch[tree[f].val < k] = tot;
maintain(tot);maintain(f);splay(tot);break;
}
}
}
int getrank(int k){
int res = 0, cur = root;
while(true){
if(k < tree[cur].val)cur = tree[cur].ch[0];
else{
res += tree[tree[cur].ch[0]].siz;
if(k == tree[cur].val){splay(cur);return res + 1;}
res += tree[cur].cnt;cur = tree[cur].ch[1];
}
}
}
int getval(int k){
int cur = root;
while(true){
if(tree[cur].ch[0] && k <= tree[tree[cur].ch[0]].siz)cur = tree[cur].ch[0];
else{k -= tree[tree[cur].ch[0]].siz + tree[cur].cnt;
if(k <= 0){splay(cur);return tree[cur].val;}
cur = tree[cur].ch[1];
}
}
}
int getpre(){
int cur = tree[root].ch[0];
if(!cur)return cur;
while(tree[cur].ch[1])cur = tree[cur].ch[1];
splay(cur);return cur;
}
int getnxt(){
int cur = tree[root].ch[1];
if(!cur)return cur;
while(tree[cur].ch[0])cur = tree[cur].ch[0];
splay(cur);return cur;
}
void remove(int k){
getrank(k);
if(tree[root].cnt > 1){tree[root].cnt–;maintain(root);return;}
if(!tree[root].ch[0] && !tree[root].ch[1]){clear(root);root = 0;return;}
if(!tree[root].ch[0]){
int cur = root;root = tree[root].ch[1];
tree[root].fa = 0;clear(cur);return;
}
if(!tree[root].ch[1]){
int cur = root;root = tree[root].ch[0];
tree[root].fa = 0;clear(cur);return;
}
int cur = root, x = getpre();
tree[tree[cur].ch[1]].fa = root;
tree[root].ch[1] = tree[cur].ch[1];
clear(cur);maintain(root);
}
int main(){
n = read();
for(int i = 1 ; i <= n ; i ++){
opt = read();x = read();
switch(opt){
case 1:insert(x);break;
case 2:remove(x);break;
case 3:write(getrank(x));putchar(‘\n’);break;
case 4:write(getval(x));putchar(‘\n’);break;
case 5:insert(x);write(tree[getpre()].val);putchar(‘\n’);remove(x);break;
case 6:insert(x);write(tree[getnxt()].val);putchar(‘\n’);remove(x);break;
default:break;
}
}
return 0;
}
Splay 操作的时间复杂度
因为 zig 和 zag 是 对称 操作，我们只需要对 zig，zig−zig，zig−zag 操作分析复杂度。采用势能分析，定义一个 $n$ 个节点的 Splay 树进行了 $m$ 次 Splay 步骤。可记 $w(x)=[\log (\mathrm{size}(x))]$, 定义势能函数为 $\phi =\sum w(x)$,$\phi (0)\le n\log n$，在第 $i$ 次操作后势能为 $\phi (i)$, 则我们只需要求出初始势能和每次的势能变化量的和即可。

由此可见，三种 Splay 步骤的势能全部可以缩放为 $\le 3(w^{\prime }(x)-w(x))$. 令 $w^{(n)}(x)=w^{\prime (n-1)}(x)$,$w^{(0)}(x)=w(x)$, 假设 Splay 操作一次依次访问了 $x_1,x_2,\cdots ,x_n$, 最终 $x_1$ 成为根节点，我们可以得到：

$$\begin{array}{rl}3\left(\sum _{i=0}^{n-2}\left(w^{(i+1)}(x_1)-w^{(i)}(x_1)\right)+w(n)-w^{(n-1)}(x_1)\right)+1& =3(w(n)-w(x_1))+1\\ & \le \log n\end{array}$$

继而可得：

$$\sum _{i=1}^m(\phi (m-i+1)-\phi (m-i))+\phi (0)=n\log n+m\log n$$

因此，对于 $n$ 个节点的 Splay 树，做一次 Splay 操作的均摊复杂度为 $O(\log n)$。因此基于 Splay 的插入，查询，删除等操作的时间复杂度也为均摊 $O(\log n)$。

​