浅谈Splay

发表于 更新于 阅读次数：
本文字数： 8.2k 阅读时长 ≈ 7 分钟

什么是 $\mathbf{Splay}$

伸展树（$Splay\quad Tree$），也叫分裂树，是一种二叉排序树，它能在 $\Theta(log_2 n)$ 内完成插入、查找和删除操作。它由丹尼尔·斯立特（ $Daniel\quad Sleator$ ） 和 罗伯特·恩卓·塔扬（ $Robert\quad Endre$ Tarjan 又是他）在 $1985$ 年发明的。
假设想要对一个二叉排序树执行一系列的查找操作。为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。 $Splay\quad tree$ 应运而生。 $Splay\quad tree$ 是一种自调整形式的二叉查找树，它会沿着从某个结点到树根之间的路径，通过一系列的旋转把这个结点搬移到树根去。

（From 百度百科）

因为 $Splay$ 是一颗二叉排序树，所以它的每一个结点都应该满足如下性质：

  • 若左子树不空，则左子树上所有结点的值均小于或等于这个结点的值。
  • 若右子树不空，则右子树上所有结点的值均大于或等于这个结点的值。

我们知道，在对二叉树进行中序遍历时，会先遍历左子树，然后是自身，最后才是右子树。所以一颗二叉排序树的中序遍历是不严格单调递增的。我们在进行重构树时，也需要保证中序遍历不变。

$\mathbf{Splay}$ 可以做什么

  • 维护一个区间（废话）。
  • 支持区间翻转。
  • 支持求一个结点的前驱和后继。
  • 支持求一个结点的排名。
  • 支持求第k大。

$\mathbf{Splay}$ 需要维护的内容

1
2
3
4
5
6
int val[N];//当前结点的值
int cnt[N];//有多少个重复结点
int pre[N];//当前结点的父结点
int siz[N];//以当前结点为根的子树大小
int son[N][2];//当前结点的子结点([0]为左儿子，[1]为右儿子)
bool rev[N];//是否翻转

$\mathbf{Splay}$ 支持的操作

$\mathbf{get_dir}$ 操作

这个操作的目的是确定一个结点是父结点的左儿子还是右儿子，返回值为 $0$ 或 $1$ 。

代码实现如下：

1
2
3
4
inline int get_dir(int x)
{
	return son[pre[x]][1]==x;
}

$\mathbf{push_up}$ 操作

这个操作的目的是更新子树大小。

代码实现如下：

1
2
3
4
5
6
inline void push_up(int x)
{
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];

	return;
}

$\mathbf{rotate} 操作

核心操作。 $Splay$ 通过旋转操作来保持平衡。
每次旋转有两种不同情况的旋转，分别是当前结点是父亲结点的左儿子和右儿子。

如果当前结点是父亲的左儿子，如下图，我们要把红点向上一层旋转：

为了方便，我们不妨令这颗树的中序遍历为 $1-2-3-4-5-6-7$ 。如下图，2号点就是我们要旋转的点：

我们可以清楚的看出 $rotate$ 的变化规律：

1
2
3
4
5
6
son[4][0]=3;
pre[3]=4;//目标结点父亲的左儿子->目标结点的右儿子
son[6][0]=2;
pre[2]=6;//目标结点爷爷的（左/右）儿子->目标结点
son[2][1]=4;
pre[4]=2;//目标结点的右儿子->目标结点的父亲

同理，我们可以看出当前结点是父亲的右儿子时的规律（图中 $6$ 号结点是目标结点）：

1
2
3
4
5
6
son[4][1]=5;
pre[5]=4;//目标结点父亲的右儿子->目标结点的左儿子
son[2][1]=6;
pre[6]=2;//目标结点爷爷的（左/右）儿子->目标结点
son[6][0]=4;
pre[4]=6;//目标结点的左儿子->目标结点的父亲

归纳一下，可以得出以下步骤：

  • 求出目标结点位于父亲结点的方向，并作为基本方向；
  • 目标结点父亲的同向儿子->目标结点的异向儿子；
  • 目标结点爷爷的（左/右）儿子->目标结点；
  • 目标结点的异向儿子->目标结点的父亲；

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void rotate(int x)
{
	int f=pre[x],g=pre[f],d=get_dir(x),s=son[x][d^1];

	son[f][d]=s;
	pre[s]=f;
	son[g][get_dir(f)]=x;
	pre[x]=g;
	son[x][d^1]=f;
	pre[f]=x;
	push_up(f);
	push_up(x);

	return;
}

$\mathbf{splay}$ 操作

这个操作的目的是将一个结点一直旋转至目标结点的儿子，如果目标结点为 $0$ ，则表示旋转至根结点。
其实只需要每次进行旋转后判断父亲是不是目标结点，如果爷爷，父亲与当前结点“三点一线”，我们就要先旋转父结点，再旋转当前结点，使这颗 $Splay$ 更平衡（这是一个很玄学的问题）。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void splay(int x,int tar=0)
{
	while(pre[x]!=tar)
	{
		int f=pre[x],g=pre[f];

		if(g!=tar)
		{
			if(get_dir(x)==get_dir(f)) rotate(f);
			else rotate(x);
		}
		rotate(x);
	}
	if(!tar) root=x;

	return;
}

$\mathbf{find}$ 操作

这是一个辅助操作，目的是把最大的小于等于指定值的结点（如果有这个值，则返回这个值，否则返回最大的小于这个值的结点） $splay$ 到根结点。
操作很简单，只需要在每个结点处判断当前结点值是否小于指定值，再决定向左或向右,最后把找到的值 $splay$ 上来。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void find(int v)
{
	int x=root;

	if(!x) return;
	while(son[x][v>val[x]]&&val[x]!=v)
	{
		x=son[x][v>val[x]];
	}
	splay(x);

	return;
}

$\mathbf{insert}$ 操作

这个操作的目的是向 $Splay$ 里插入一个值。
和上一个操作类似，也是 需要在每个结点处判断当前结点值是否小于指定值，再决定向左或向右，如果结点存在则直接自增 $cnt$ 的值。否则新建结点并与父结点连边。
因为新建结点时可能会拉出一条链，为了保持 $Splay$ 的平衡，我们需要将该结点 $splay$ 到根。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void insert(int v)
{
	int x=root,f=0;

	while(x&&val[x]!=v)
	{
		f=x;
		x=son[x][v>val[x]];
	}
	if(x) ++cnt[x];
	else
	{
		x=(++ncnt);
		if(f) son[f][v>val[f]]=x;
		val[x]=v;
		cnt[x]=1;
		pre[x]=f;
		siz[x]=1;
		son[x][0]=0;
		son[x][1]=0;
	}
	splay(x);

	return;
}

$\mathbf{kth}$ 操作

显然，这个操作是求第 $k$ 大的数。
同样是从根结点开始向下搜，每次需要判断 $k$ 与左子树大小，与（左子树大小 $+$ 该结点 $cnt$ ）的大小关系，再决定向左或向右，或是返回这个结点。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int kth(int ord)
{
	int x=root;

	while(true)
	{
		if(son[x][0]&&ord<=siz[son[x][0]]) x=son[x][0];
		else if(ord>siz[son[x][0]]+cnt[x])
		{
			ord-=(siz[son[x][0]]+cnt[x]);
			x=son[x][1];
		}
		else return x;
	}

	return -1;
}

$\mathbf{rank}$ 操作

返回指定值的排名。
只需要把这个值转到根，再返回根结点左子树大小即可。

代码实现如下：

1
2
3
4
5
int rank(int v)
{
	find(v);
	return siz[son[root][0]];
}

prev 操作

求指定值的前驱（比它小的数中最大的）。
只需要找到左子树中最右边的那一个，返回即可。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
int prev(int v)
{
	int u;

	find(v);
	u=son[root][0];
	while(son[u][1]) u=son[u][1];

	return u;
}

$\mathbf{succ}$ 操作

求指定值的后继（比它大的数中最小的）。
同理，只需要找到右子树中最左边的那一个，返回即可。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
int succ(int v)
{
	int u;

	find(v);
	u=son[root][1];
	while(son[u][0]) u=son[u][0];

	return u;
}

$\mathbf{remove}$ 操作

删除指定值。
如图，可以看出，如果把 $prev(x)\quad splay$ 到根结点，把 $succ(x)\quad splay$ 到 $prev(x)$ 的右儿子，那么 $succ(x)$ 的左儿子只会有目标结点一个结点，删除方法显而易见。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void remove(int v)
{
	int p=prev(v),s=succ(v),tar;

	splay(p);
	splay(s,p);
	tar=son[p][0];
	if(cnt[tar]>1)
	{
		--cnt[tar];
		splay(tar);
	}
	else son[p][0]=0;

	return;
}

$\mathbf{reverse}$ 操作

区间翻转， $Splay$ 的标准操作之一。
和线段树区间加一样，这个地方也运用了“懒标记”的思想。和 $remove$ 操作类似，将 $[L,R]$ 区间提取出来，可以把 $L-1\quad splay$ 到根结点，把 $R+1\quad splay$ 到根结点的儿子，如图。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
void reverse(int l,int r)
{
	int f=kth(l),s=kth(r+2);//因为prev，succ都是相对值，所以初始化要插入一个极大值和一个极小值。

	splay(f);
	splay(s,f);
	rev[son[s][0]]^=1;

	return;
}

同时我们需要将标记下方，于是我们需要 $push_down$ 操作。在每次标记下放时交换左右儿子；

代码实现如下：

1
2
3
4
5
6
7
8
9
10
inline void push_down(int x)
{
	if(!rev[x]) return;
	swap(son[x][0],son[x][1]);
	rev[son[x][0]]^=1;
	rev[son[x][1]]^=1;
	rev[x]=0;

	return;
}

继续思考，我们什么时候需要下放标记？当且仅当翻转前后对答案有影响。在上述操作中，只有求第 $k$ 大（ $kth$ 操作）会有影响，因此，我们需要修改 $kth$ 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int kth(int ord)
{
	int x=root;

	while(true)
	{
		push_down(x);//新增
		if(son[x][0]&&ord<=siz[son[x][0]]) x=son[x][0];
		else if(ord>siz[son[x][0]]+cnt[x])
		{
			ord-=(siz[son[x][0]]+cnt[x]);
			x=son[x][1];
		}
		else return x;
	}

	return -1;
}

$\mathbf{output}$ 操作

最后一个操作，输出！
注意输出时要下放标记。

代码实现如下：

1
2
3
4
5
6
7
8
9
10
void output(int x)
{
	push_down(x);
	if(son[x][0]) output(son[x][0]);
	if(abs(val[x])!=inf)
		while(cnt[x]--) printf("%d ",val[x]);
	if(son[x][1]) output(son[x][1]);

	return;
}

结语

$Splay$ 还可以实现更多操作，大都与区间打标记有关。 $Splay$ 标记下放与线段树类似，类比即可。

最后放一下模板题：LGOJ P3391 【模板】文艺平衡树（Splay）

std:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
#include <cmath>
#include <cstdio>
#include <algorithm>
using std::swap;
#define inf 0x3f3f3f3f

int ncnt=0,root=0,val[100005],cnt[100005],pre[100005],siz[100005],son[100005][2];
bool rev[100005];

inline int get_dir(int x)
{
	return son[pre[x]][1]==x;
}

inline void push_up(int x)
{
	siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x];

	return;
}

inline void push_down(int x)
{
	if(!rev[x]) return;
	swap(son[x][0],son[x][1]);
	rev[son[x][0]]^=1;
	rev[son[x][1]]^=1;
	rev[x]=0;

	return;
}

inline void rotate(int x)
{
	int f=pre[x],g=pre[f],d=get_dir(x),s=son[x][d^1];

	son[f][d]=s;
	pre[s]=f;
	son[g][get_dir(f)]=x;
	pre[x]=g;
	son[x][d^1]=f;
	pre[f]=x;
	push_up(f);
	push_up(x);

	return;
}

void splay(int x,int tar=0)
{
	while(pre[x]!=tar)
	{
		int f=pre[x],g=pre[f];

		if(g!=tar)
		{
			if(get_dir(x)==get_dir(f)) rotate(f);
			else rotate(x);
		}
		rotate(x);
	}
	if(!tar) root=x;

	return;
}

void find(int v)
{
	int x=root;

	if(!x) return;
	while(son[x][v>val[x]]&&val[x]!=v)
	{
		x=son[x][v>val[x]];
	}
	splay(x);

	return;
}

void insert(int v)
{
	int x=root,f=0;

	while(x&&val[x]!=v)
	{
		f=x;
		x=son[x][v>val[x]];
	}
	if(x) ++cnt[x];
	else
	{
		x=(++ncnt);
		if(f) son[f][v>val[f]]=x;
		val[x]=v;
		cnt[x]=1;
		pre[x]=f;
		siz[x]=1;
		son[x][0]=0;
		son[x][1]=0;
	}
	splay(x);

	return;
}

int kth(int ord)
{
	int x=root;

	while(true)
	{
		push_down(x);
		if(son[x][0]&&ord<=siz[son[x][0]]) x=son[x][0];
		else if(ord>siz[son[x][0]]+cnt[x])
		{
			ord-=(siz[son[x][0]]+cnt[x]);
			x=son[x][1];
		}
		else return x;
	}

	return -1;
}

int rank(int v)
{
	find(v);
	return siz[son[root][0]];
}

int prev(int v)
{
	int u;

	find(v);
	u=son[root][0];
	while(son[u][1]) u=son[u][1];

	return u;
}

int succ(int v)
{
	int u;

	find(v);
	u=son[root][1];
	while(son[u][0]) u=son[u][0];

	return u;
}

void remove(int v)
{
	int p=prev(v),s=succ(v),tar;

	splay(p);
	splay(s,p);
	tar=son[p][0];
	if(cnt[tar]>1)
	{
		--cnt[tar];
		splay(tar);
	}
	else son[p][0]=0;

	return;
}

void reverse(int l,int r)
{
	int f=kth(l),s=kth(r+2);

	splay(f);
	splay(s,f);
	rev[son[s][0]]^=1;

	return;
}

void output(int x)
{
	push_down(x);
	if(son[x][0]) output(son[x][0]);
	if(abs(val[x])!=inf)
		while(cnt[x]--) printf("%d ",val[x]);
	if(son[x][1]) output(son[x][1]);

	return;
}

int main()
{
    int n,m;

	scanf("%d%d",&n,&m);

	insert(-inf);
	insert(inf);
	for(register int i=1;i<=n;++i) insert(i);

	while(m--)
	{
		int L,R;

		scanf("%d%d",&L,&R);

		reverse(L,R);
	}

	output(root);
	return 0;
}