Splay

缘起

【1】中讲解了AVL这种平衡查找树. 它的一大亮点就是不论你插入的数据倾斜程度有多么的严重, 都可以通过一系列的自旋操作将树的深度维持在O(logn). 进而使得BST哪怕在最坏情况下搜索的复杂度也维持在O(logn). 这是一种理想状态. 我们从【1】中的代码看到，仅仅是增加和删除就已经非常复杂了（可以说插入一个元素将耗费大量的CPU在自旋操作上）. 我们扪心自问——真的有必要吗? 举一个常识——你想读书看报、和周围人自由的交流，你有必要认识全部的8万个汉字吗,其实常用的汉字只有3500字而已. 这3500汉字已经足以覆盖近乎99%的中文材料了. 所以我们一个自然的想法是——舍弃绝对的平衡, 而将常用的数据离根节点近一点（因为日常用的数据符合28定律, 即80%使用频率的数据仅仅占据20%的总数据量）, 则总体而言, 搜索算法的均摊复杂度亦可以到达O(logn).

注意，不要小看离根节点近一点，在数据爆炸的今天，内存算法近乎不可能，多为外算法甚至分布式算法. 所以一次节点的跳转选择就意味着一次磁盘IO甚至网络IO, 众所周知，网络IO、磁盘IO远远低于内存读写，更远远低于CPU运算. 所以减少IO, 让常用的那80%的数据离根节点近一点成为提高算法性能的关键，而”离根节点近一点”就是这里的伸展操作. 也就是下面的模板中 splay2 函数. 所谓常用，就是本次操作的结果. 但是相比平衡查找树， 伸展树实现简便、无需修改节点 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要O(n)时间，故难以适用于核电站、医院等对可靠性和稳定性要求极高的场合。反之，【1】中的AVL树尽管可以保证最坏情况下的单次操作速度，但需在节点中嵌入平衡因子等标识；更重要的是， 删除操作之后的重平衡可能需做多 达O(logn)次旋转， 从而频繁地导致全树整体拓扑结构的大幅度变化。

分析

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
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996)
//#define LOCAL
using namespace std;

const int MAXN = 10; // splay树中最多10个顶点

struct SplayNode // 伸展树节点的数据结构
{
	// key是顶点的值, size是本节点为根节点的树的大小(重复出现的话, 要按次数计算的, 不能只算1次，而是出现多少次就要计多少次),cnt是本节点的计次数.lson是左孩子在splay数组中的索引, rson是右孩子在splay数组中的索引,parent是父节点的索引, 对于根节点的parent就是0
	int key, size, cnt, lson, rson, parent;
}splay[MAXN]; // 0索引不用于存储数据（因为根节点的parent是0） 这里使用数组这种连续的数据结构实现伸展树,有些博客使用的是链表, 本质没有什么区别. 

int tot, root; // tot是splay数组中元素的个数.root是splay数组的根节点所在的索引

void updatesize(int k) {splay[k].size = splay[splay[k].rson].size+splay[splay[k].lson].size+splay[k].cnt;} // 更新splay[k]的size域

void leftrotate(int k) // 左旋 splay[k]  参见图1
{
	int P = splay[k].parent; // 图1中的P 即父节点
	int G = splay[P].parent; // 祖父
	splay[P].rson = splay[k].lson;
	if (splay[k].lson) splay[splay[k].lson].parent = P;
	splay[k].parent = G;
	if (G)
	{
		if (splay[G].lson == P) splay[G].lson = k;
		else splay[G].rson = k;
	}
	splay[k].lson = P;
	splay[P].parent = k;
	splay[k].size = splay[P].size; // 调整size
	updatesize(P);
}

void rightrotate(int k)   // 右旋splay[k] 参见 图2
{
	int P = splay[k].parent;
	int G = splay[P].parent;
	splay[P].lson = splay[k].rson;
	if (splay[k].rson) splay[splay[k].rson].parent = P;
	splay[k].parent = G;
	if (G)
	{
		if (P == splay[G].lson) splay[G].lson = k;
		else splay[G].rson = k;
	}
	splay[k].rson = P;
	splay[P].parent = k;
	splay[k].size = splay[P].size;
	updatesize(P);
}

void splay2(int k, int target) // 伸展树的核心操作之伸展, 即将splay[k]伸展至splay[target]的儿子节点位置，例如target=0的话, 就表示伸展到根节点，所谓伸展指的就是 splay[target]的儿子是splay[k]
{ // 因为该操作形象的说, 就是从孙子节点翻转到父节点, 然后从父节点翻转到爷爷节点, 一层一层的往上转，就像杨柳枝不断的被风吹的伸开了树枝一样, 所以伸展树的名称由此得来.
	while(splay[k].parent != target) // 只要还没伸展到位置， 就继续伸展
	{
		int P = splay[k].parent; // 父亲
		int G = splay[P].parent; // 祖父
		// 下面的操作是只有呈一字型, 才进行两次旋转，否则都只进行一次旋转
		if (k == splay[P].lson) // 如果K是P的左孩子
		{ // 如果G是目标了或者P是G的右孩子，则都不会进行绕P的右旋, 因为对于G是目标的话, 直接绕k右旋，让k和P交换位置就达到了k成为目标顶点的孩子的目的, 如果P是G的右孩子, 则也只需要绕k右旋即可. 则k和P交换位置. 如果k是P的左孩子、P是G的左孩子, 则要做两次右旋, 先绕P，再绕k
			if (G!=target && P == splay[G].lson) rightrotate(P); // 如果祖父也不是target, 并且P是G的左孩子 则绕P右旋
			rightrotate(k); // 绕k右旋
		}
		else // K是P的右孩子
		{
			if (G!=target && P == splay[G].rson) leftrotate(P);
			leftrotate(k);
		}
	} // 最后k的父节点就是target
	if (!target) root = k; // 对于target为0的情况下, 要更新root索引
}

int create(int key,int parent) // 创建一个伸展树节点, 该节点的数据是key, 父节点是parent, 当然，后续肯定要修改的，因为一个很显然的问题——如果在原先的伸展树中存在key的话, 怎么办? 见下面的insert方法
{
	tot++;
	splay[tot].cnt = splay[tot].size = 1;
	splay[tot].key = key;
	splay[tot].lson = splay[tot].rson = 0;
	splay[tot].parent = parent;
	return tot;
}

void insert(int key)
{
	if (!root)
	{
		root = create(key,0);
		return;
	}
	int k = root, y=0; // k是下探指针, y是最后插入的key在伸展树中的索引
	while(true)
	{
		splay[k].size++;
		if (key == splay[k].key)
		{
			splay[k].cnt++;
			y = k; // 如果插入了一个已经存在的值的话, 则就准备把这个已经存在的节点伸展到根节点去.
			break;
		}
		else if(key < splay[k].key)
		{
			if (splay[k].lson) k = splay[k].lson; // 继续
			else // 到此为止
			{
				y = splay[k].lson = create(key, k);
				break;
			}
		}
		else
		{
			if (splay[k].rson) k = splay[k].rson;
			else
			{
				y = splay[k].rson = create(key, k);
				break;
			}
		}
	}
	splay2(y, 0); // 上述插入完毕之后，新插入的节点通过伸展操作旋转至根节点
}

int find(int key) // 返回要查找的节点在伸展树数组中的索引，如果不存在, 返回0
{
	if (!root) return 0; // 如果是空树的话
	int k = root, y =0; // y是key所在节点的索引
	while(true)
	{
		if (key == splay[k].key) // 找到了
		{
			y = k;
			break;
		}
		else if (key < splay[k].key) // 往左子树继续找
		{
			if(splay[k].lson) k = splay[k].lson; // 存在左子树就继续, 否则y保持为0(表示没有找到)
			else break;
		}
		else
		{
			if (splay[k].rson) k  =splay[k].rson;
			else break;
		}
	}
	splay2(k,0); // 因为你这次找的是k, 所以查找完毕之后要将k(最接近key的那个索引)伸展至根节点位置.
	return y; // 伸展操作改变的仅仅是splay[xxx]中的parent、lson、rson、size值, 并不改变 splay[xxx].key、splay[xxx].count, 所以不用担心返回y之后, 用户使用splay[y].key 得不到他想得到的数据,所以索引只取决于输入数据的顺序, 但是树的结构可能在随着用户的操作而不停的变化呢
}

int getmin(int x) // 求取以x为根节点的伸展树中的最小值，返回这个最小值所在节点在splay中的索引
{
	int k = splay[x].parent; // 因为下面x要变到最小节点所在索引去, 所以要暂存x的父节点,以便最后伸展
	while(splay[x].lson) x=splay[x].lson; // splay 依旧是bst, 所以一路向左是可以求取最小值所在节点的索引的
	splay2(x,k); // 伸展x到k处, 因为你查了最小值, 所以要将x伸展
	return x;
}

void del(int key) // 删除关键字key
{
	if (!root) return; // 空树删个屁
	int x = find(key); // 先找, 注意，如果找到了的话, 就已经将目标旋转至根节点了, 即root=x
	if (!x) return; // 没找到, 删个屁
	if(splay[x].cnt>1) // 如果有多于一个,则减数完事儿走人
	{
		splay[x].cnt--;
		splay[x].size--;
		return;
	}
	if (!splay[x].lson && !splay[x].rson) // 如果就是一个光杆司令
	{
		root = tot = 0;
		return;
	}
	if (!splay[x].lson && splay[x].rson) // 如果左孩子没有，只有右孩子
	{
		root = splay[x].rson; // 右孩子成为根节点
		splay[splay[x].rson].parent = 0;
		return;
	}
	if (!splay[x].rson && splay[x].lson)
	{
		root = splay[x].lson;
		splay[splay[x].lson].parent = 0;
		return;
	}
	// 如果既有左孩子、又有右孩子， 则删除root=x之后，就应该把root的右子树的最左的孩子伸展为根节点, 而最左孩子就是getmin返回值嘛. getmin过程中, 这个最左孩子将成为右子树的根节点
	root = getmin(splay[x].rson);
	splay[root].parent = 0;
	splay[root].lson = splay[x].lson; // 新根的左孩子=老根的左孩子
	splay[splay[x].lson].parent = root; // 老根左孩子的新爸爸是root. 注意,老根右孩子的新爸爸是root这件事情在getmin的时候已经做了
	updatesize(root);
}

int rnk(int key) // 求key的排名, 注意，伸展树中未必有此值
{
	int k = find(key);
	if (!k) return 0; // 返回0表示不存在
	return splay[splay[k].lson].size+1; // 所以如果key值不止一个的话 输出最靠前的排名
}

int kth(int k) // 从小到大排名k的关键字所在索引
{
	if (!root || k > splay[root].size) return 0; // 不存在
	int	x = root; // 从根节点开始找
	while(1)
	{
		if (splay[splay[x].lson].size < k && k<=splay[splay[x].lson].size+splay[x].cnt) break;
		else if (k<=splay[splay[x].lson].size) x= splay[x].lson;
		else
		{
			k-=(splay[splay[x].lson].size+splay[x].cnt);
			x = splay[x].rson;
		}
	} // 最后x就是排名第k小的元素的索引
	splay2(x,0); // 伸展x到根节点
	return x;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in","r",stdin);
#endif

	int a[]={10,2,2,2,2,3,3,10},i,x,n=sizeof(a)/sizeof(int);//n是数组a含有的元素个数
	//测试insert模块(整个过程参见 图3)
	for ( i = 0; i < n; i++) insert(a[i]);//逐个插入关键字
	//测试Find模块
	puts("输入你想查询的关键字");
	scanf_s("%d",&x);
	int index =find(x);
	if (!index) puts("您要查找的关键字不存在");//如果不存在,注意,执行完Find之后,伸展树也会调整的	
	else printf("存在哦,它的索引是%d\n", index);
	//测试getmin模块
	printf("这棵伸展树最小元是%d\n",splay[getmin(root)].key);//注意,对整伸展树执行GetMin之后,最小元跑到根节点去了
	//测试rank模块
	puts("输入您要查询的关键字,程序将输出它在伸展树中的排名(如果有多个这个关键字,输出的是这个关键字的最靠前的排名)");
	scanf_s("%d",&x);
	if (!rnk(x)) puts("你要找的关键字不存在");//如果不存在	
	else printf("%d在伸展树中的排名是%d\n",x,rnk(x));
	//测试kth模块
	puts("输入您要查找的排名");
	scanf_s("%d",&x);
	printf("排名是%d的关键字是%d\n",x,kth(x));
	//测试del模块
	for ( i = 0; i < n; i++)del(a[i]);		  
	return 0;
}

附录

​ 图1

​ 图2

​ 图3

参考

【1】https://yfsyfs.github.io/2019/05/28/AVL/