普通平衡树

学习
字数统计: 4.6k   |   阅读时长≈ 19 分钟

Splay-普通平衡树

0. 概述

  • 二叉查找树(Binary Search Tree, BST)是一种能存储特定数据类型的容器。二叉查找树允许快速查找、插入或者删除某一个节点。重要性质：左小右大，中序遍历是有序的。
image-20240215072453341
  • Splay（伸展树）是一种平衡二叉树，通过不断将某个节点旋转到根节点，使得整棵树仍然满足BST的性质，并且保持平衡而不至于退化为链。

1. 数据结构

2. 旋转 rotate

  • 旋转分为右旋和左旋，如下图中将x旋转上升到y的位置，右旋即沿顺时针方向旋转，x、y的父子关系发生改变，同时因为a、b本身是x的孩子，所以b旋转后变成y的孙子，a还是x的孩子。
  • 特点：右旋，把x的右孩子给y；左旋，把x的左孩子给y。
  • 左旋和右旋后，信息是保序且正确的，即中序遍历得到的结果是相同的。
  • pushup函数用于自下往上传递每个节点维护的子树大小。
image-20240215072739091 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 从自下往上push,由子节点的信息算出父节点的信息
// 因为旋转后x/y两个节点对应的子树大小有所改变,所以需要更新
void pushup(int x) {
	// 左孩子size+右孩子size+该点可能插入多次的cnt值
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}

// rotate函数把左旋和右旋归纳到一起了,所以操纵的时候用tr[y].s[k]
void rotate(int x) {
	int y=tr[x].p,z=tr[y].p; // 取出x的父节点y以及父节点的父节点z
	int k=tr[y].s[1]==x; // 如果x是y的右儿子,那么k取1,k的值决定左旋还是右旋,k=0左旋,=1右旋
	// 下面两行在处理旋转后x的孩子和y的树边	
	// 注意,0^1=1,1^0=0,所以选择异或操作
	tr[y].s[k]=tr[x].s[k^1]; // y节点的左/右(看k为多少)孩子变为x的右/左孩子,x把孩子送走,变成孙子节点
	tr[tr[x].s[k^1]].p=y; // 树边是双向的,再把x的孩子的父亲变成y
	// 下面两行在处理旋转后x/y的树边
	tr[x].s[k^1]=y;
	tr[y].p=x;
	// 下面两行在处理旋转后x/z的树边
	tr[z].s[tr[z].s[1]==y]=x;
	tr[x].p=z;
	// 其他边是不受影响的
	pushup(y),pushup(x);
}

3. 伸展 splay

  • 平衡树的核心操作，每访问一个节点x，就把x旋转到根节点，有三种情况
  • 对于双旋操作注意，直线型第一次转中间的y，第二次转底下的x；折线形第一次转底下的x，第二次也转x，故有直转中，折转底
image-20240215075040613 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 把x旋转到k的下面,即x要当k的儿子
// k>0时,把x转到k的下面
// k=0时,把x转到根
void splay(int x,int k) {
	// 当x的父亲等于k的时候结束
	while(tr[x].p!=k) {
		int y=tr[x].p,z=tr[y].p; // 取出x的父节点y和父节点的父节点z
		// z!=k,说明y不是根,做双旋
		// 折线形转底,直线型转中,可以看图例
		if(z!=k) 
			// 如果都做左孩子/右孩子,说明直线型,旋转底下的x
			// 如果一个左一个右,形成折线形,旋转中间的y
			(tr[y].s[0]==x)^(tr[z].s[0]==y) ? rotate(x) : rotate(y);	
		rotate(x); // z!=k,则最后还要旋转x;z==k,本来也要旋转x
	}
	// k=0是一个不存在的节点,即根节点的父节点,所以相当于把x转到根,最后更新一下根节点
	// 因为所有操作都是基于根节点进行的,所以对根节点进行更新
	if(k==0) root=x;
}

4. 查找 find

  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
11
// 查找,找到v(v是权值)所在节点,并把该节点转到根
// 如果找不到这个值,是把与这个点最接近的点转到根上去
void find(int v) {
	int x=root; // 取根节点
	// 要么x的哪个儿子为空了(走到空节点上了),要么找的v的值已经等于x的值了,退出循环
	// 这个while循环是从根节点去找v这个值,如果大于他,走左子树找较小值/如果小于他,走右子树找较大值
	// 如果找不到这个值,是把与这个点最接近的点转到根上去
	while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
		x=tr[x].s[v>tr[x].v];
	splay(x,0);
}

5. 前驱 get_pre

  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 求前驱,求v的前驱,v是权值嗷,返回其节点编号
// 如果v在树中是不存在的,那么根据上面的find函数,我们能够成功返回一个最靠近这个不存在的v的前驱
int get_pre(int v) {
	find(v); // 先找到这个点,转到根上去,如果不存在,找到的是略大于v的不存在的点
	int x=root;
	// 此时v已经旋转到根节点了,如果v比根节点大,那么前驱就是x
	if(tr[x].v<v) return x;
	// 否则,去左子树上找
	x=tr[x].s[0]; // 找前驱嘛,比它小且最近的那肯定在左子树上啊
	// 左子树上最大最靠近我们要找的前驱的值肯定在右子树上,所以沿着右子树走
	while(tr[x].s[1]) x=tr[x].s[1]; 
	// 查完前驱后也旋转一次
	splay(x,0);
	return x;
}

6. 后继 get_suc

  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
11
// 找后继
int get_suc(int v) {
	find(v);
	int x=root;
	if(tr[x].v>v) return x;
	x=tr[x].s[1];
	while(tr[x].s[0]) x=tr[x].s[0];
	// 查完后继后旋转
	splay(x,0);
	return x;
}

7. 删除 del

  • 删除的时候用到一个技巧，比如6、8、9中欲删除8，6是8是前驱，9是8的后继，可以先找到前驱和后继再把8夹住，这样8变成叶子节点，就方便直接删除
image-20240215082014315
  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 删除(若有多个相同的数,只删除一个)
// 要删除一个节点找边的关系实在过于麻烦不好找,因此我们选择把前驱转到根节点
// 再把后继转到根节点的下面,此时要删的这个点就被夹击了,那么它只能作为叶子节点
// 作为叶子节点就好切割了
void del(int v) {
	// 找前驱和后继的编号
	int pre=get_pre(v);
	int suc=get_suc(v);
	// 前驱转到根,后继到前驱的下边
	splay(pre,0),splay(suc,pre);
	// 这样就获取到了要删除的节点的编号
	int del=tr[suc].s[0];
	// 如果个数大于1,那么删除一个,再把del转到根,这样的目的是splay触发rotate,rotate触发pushup更新大小等
	if(tr[del].cnt>1)
		tr[del].cnt--, splay(del,0);
	// 如果恰好只有一个,直接把这个点清空(即切断叶子节点),把叶子节点以上的节点更新一下,所以splay(suc,0)
	else
		tr[suc].s[0]=0, splay(suc,0);
}

8. 插入 insert

  • 注意要通过insert来插入哨兵，保证最小值有前驱，最大值有后继，这样每个节点都可以看作独立且统一的了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 插入函数,可用于初始化
void insert(int v) {
	int x=root, p=0; // 从跟上走,p记录其父节点
	// 要么x==0(走到空间点)或者已经找到这个值(重复插入多次时)
	while(x&&tr[x].v!=v)
		p=x,x=tr[x].s[v>tr[x].v]; // v>tr[x].v走右子树,否则走左子树
	if(x) tr[x].cnt++; // x!=0,则个数+1
	// 否则x是一个空节点,那么初始化一下再插入到这个树中,就是说这个点没有出现过
	else {
		x=++idx; // 给x一个新的编号
		tr[p].s[v>tr[p].v]=x; // 建边关系
		tr[x].init(p,v); // 更新节点信息
	}
	splay(x,0); // 转一下,改善平衡性的同时用pushup更新大小
}

9. 排名 get_rank

  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
// 排名,查询v数的排名
int get_rank(int v) {
	// 注释掉的代码改成下面的,因为有可能v这个数值是不存在的,所以先插入再删除
//	find(v); // v找到,转到根上去,返回左子树的大小就是排名(在中序遍历中)
//	return tr[tr[root].s[0]].size; // 为什么不加1?因为有哨兵,极大值和极小值
	insert(v);
	int res=tr[tr[root].s[0]].size;
	del(v);
	return res;
}

10. 取值 get_val

  • 直接看注释吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 取数值,查询排名为k的数值
int get_val(int k) {
	int x=root; // 取根
	while(1) {
		int y=tr[x].s[0]; // 取左孩子
		// 如果左子树加上根的总大小小于k,说明k很大,应该在右子树上找,否则在左子树上找
		if(tr[y].size+tr[x].cnt<k) {
			k-=tr[y].size+tr[x].cnt; // 减去左子树大小加上根节点.cnt,求出旋转后正确的k值
			x=tr[x].s[1]; // x走到右儿子上去
		} 
		// 如果tr[y].size>=k了就往左子树上走
		else if(tr[y].size>=k) x=y;	
		// 既不往左子树上走,也不往根子树上找,说明已经找到这个点
		else break;
	}
	// 每找一个树转一下
	splay(x,0);
	return tr[x].v;
}

11. 例题

洛谷：P3369 【模板】普通平衡树

image-20240215091357163 image-20240215091405693 
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
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 

const int N=1e5+5;

struct node {
	int s[2]; // 存左右儿子,s[0]:左孩子,s[1]:右孩子
	int p; // 父节点
	int v; // 该节点权值
	int cnt; // 权值出现的次数,cnt=1,这个树只出现过一次,cnt>=1,出现过多次
	int size; // 子树大小
	// 初始化,每插入一个节点对其初始化信息
	void init(int p1,int v1) {
		p=p1,v=v1;
		cnt=size=1;
	}
}tr[N];
int root; // 根节点编号
int idx; // 建树遍历因子

// 从自下往上push,由子节点的信息算出父节点的信息
// 因为旋转后x/y两个节点对应的子树大小有所改变,所以需要更新
void pushup(int x) {
	// 左孩子size+右孩子size+该点可能插入多次的cnt值
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;
}

// rotate函数把左旋和右旋归纳到一起了,所以操纵的时候用tr[y].s[k]
void rotate(int x) {
	int y=tr[x].p,z=tr[y].p; // 取出x的父节点y以及父节点的父节点z
	int k=tr[y].s[1]==x; // 如果x是y的右儿子,那么k取1,k的值决定左旋还是右旋,k=0左旋,=1右旋
	// 下面两行在处理旋转后x的孩子和y的树边	
	// 注意,0^1=1,1^0=0,所以选择异或操作
	tr[y].s[k]=tr[x].s[k^1]; // y节点的左/右(看k为多少)孩子变为x的右/左孩子,x把孩子送走,变成孙子节点
	tr[tr[x].s[k^1]].p=y; // 树边是双向的,再把x的孩子的父亲变成y
	// 下面两行在处理旋转后x/y的树边
	tr[x].s[k^1]=y;
	tr[y].p=x;
	// 下面两行在处理旋转后x/z的树边
	tr[z].s[tr[z].s[1]==y]=x;
	tr[x].p=z;
	// 其他边是不受影响的
	pushup(y),pushup(x);
}

// 把x旋转到k的下面,即x要当k的儿子
// k>0时,把x转到k的下面
// k=0时,把x转到根
void splay(int x,int k) {
	// 当x的父亲等于k的时候结束
	while(tr[x].p!=k) {
		int y=tr[x].p,z=tr[y].p; // 取出x的父节点y和父节点的父节点z
		// z!=k,说明y不是根,做双旋
		// 折线形转底,直线型转中,可以看图例
		if(z!=k) 
			// 如果都做左孩子/右孩子,说明直线型,旋转底下的x
			// 如果一个左一个右,形成折线形,旋转中间的y
			(tr[y].s[0]==x)^(tr[z].s[0]==y) ? rotate(x) : rotate(y);	
		rotate(x); // z!=k,则最后还要旋转x;z==k,本来也要旋转x
	}
	// k=0是一个不存在的节点,即根节点的父节点,所以相当于把x转到根,最后更新一下根节点
	// 因为所有操作都是基于根节点进行的,所以对根节点进行更新
	if(k==0) root=x;
}

// 查找,找到v(v是权值)所在节点,并把该节点转到根
// 如果找不到这个值,是把与这个点最接近的点转到根上去
void find(int v) {
	int x=root; // 取根节点
	// 要么x的哪个儿子为空了(走到空节点上了),要么找的v的值已经等于x的值了,退出循环
	// 这个while循环是从根节点去找v这个值,如果大于他,走左子树找较小值/如果小于他,走右子树找较大值
	// 如果找不到这个值,是把与这个点最接近的点转到根上去
	while(tr[x].s[v>tr[x].v]&&v!=tr[x].v)
		x=tr[x].s[v>tr[x].v];
	splay(x,0);
}

// 求前驱,求v的前驱,v是权值嗷,返回其节点编号
// 如果v在树中是不存在的,那么根据上面的find函数,我们能够成功返回一个最靠近这个不存在的v的前驱
int get_pre(int v) {
	find(v); // 先找到这个点,转到根上去,如果不存在,找到的是略大于v的不存在的点
	int x=root;
	// 此时v已经旋转到根节点了,如果v比根节点大,那么前驱就是x
	if(tr[x].v<v) return x;
	// 否则,去左子树上找
	x=tr[x].s[0]; // 找前驱嘛,比它小且最近的那肯定在左子树上啊
	// 左子树上最大最靠近我们要找的前驱的值肯定在右子树上,所以沿着右子树走
	while(tr[x].s[1]) x=tr[x].s[1]; 
	// 查完前驱后也旋转一次
	splay(x,0);
	return x;
}

// 找后继
int get_suc(int v) {
	find(v);
	int x=root;
	if(tr[x].v>v) return x;
	x=tr[x].s[1];
	while(tr[x].s[0]) x=tr[x].s[0];
	// 查完后继后旋转
	splay(x,0);
	return x;
}

// 删除(若有多个相同的数,只删除一个)
// 要删除一个节点找边的关系实在过于麻烦不好找,因此我们选择把前驱转到根节点
// 再把后继转到根节点的下面,此时要删的这个点就被夹击了,那么它只能作为叶子节点
// 作为叶子节点就好切割了
void del(int v) {
	// 找前驱和后继的编号
	int pre=get_pre(v);
	int suc=get_suc(v);
	// 前驱转到根,后继到前驱的下边
	splay(pre,0),splay(suc,pre);
	// 这样就获取到了要删除的节点的编号
	int del=tr[suc].s[0];
	// 如果个数大于1,那么删除一个,再把del转到根,这样的目的是splay触发rotate,rotate触发pushup更新大小等
	if(tr[del].cnt>1)
		tr[del].cnt--, splay(del,0);
	// 如果恰好只有一个,直接把这个点清空(即切断叶子节点),把叶子节点以上的节点更新一下,所以splay(suc,0)
	else
		tr[suc].s[0]=0, splay(suc,0);
}

// 插入函数,可用于初始化
void insert(int v) {
	int x=root, p=0; // 从跟上走,p记录其父节点
	// 要么x==0(走到空间点)或者已经找到这个值(重复插入多次时)
	while(x&&tr[x].v!=v)
		p=x,x=tr[x].s[v>tr[x].v]; // v>tr[x].v走右子树,否则走左子树
	if(x) tr[x].cnt++; // x!=0,则个数+1
	// 否则x是一个空节点,那么初始化一下再插入到这个树中,就是说这个点没有出现过
	else {
		x=++idx; // 给x一个新的编号
		tr[p].s[v>tr[p].v]=x; // 建边关系
		tr[x].init(p,v); // 更新节点信息
	}
	splay(x,0); // 转一下,改善平衡性的同时用pushup更新大小
}

// 排名,查询v数的排名
int get_rank(int v) {
	// 注释掉的代码改成下面的,因为有可能v这个数值是不存在的,所以先插入再删除
//	find(v); // v找到,转到根上去,返回左子树的大小就是排名(在中序遍历中)
//	return tr[tr[root].s[0]].size; // 为什么不加1?因为有哨兵,极大值和极小值
	insert(v);
	int res=tr[tr[root].s[0]].size;
	del(v);
	return res;
}

// 取数值,查询排名为k的数值
int get_val(int k) {
	int x=root; // 取根
	while(1) {
		int y=tr[x].s[0]; // 取左孩子
		// 如果左子树加上根的总大小小于k,说明k很大,应该在右子树上找,否则在左子树上找
		if(tr[y].size+tr[x].cnt<k) {
			k-=tr[y].size+tr[x].cnt; // 减去左子树大小加上根节点.cnt,求出旋转后正确的k值
			x=tr[x].s[1]; // x走到右儿子上去
		} 
		// 如果tr[y].size>=k了就往左子树上走
		else if(tr[y].size>=k) x=y;	
		// 既不往左子树上走,也不往根子树上找,说明已经找到这个点
		else break;
	}
	// 每找一个树转一下
	splay(x,0);
	return tr[x].v;
}

int n;

int main() {
	insert(-1e9);insert(1e9); // 插入哨兵
	cin>>n;
	while(n--) {
		int op,x;
		scanf("%d%d",&op,&x);
		if(op==1) insert(x);
		if(op==2) del(x);
		// 对于操作356不保证当前数据结构中存在数x
		if(op==3) printf("%d\n",get_rank(x));
		if(op==4) printf("%d\n",get_val(x+1)); // 因为哨兵中有极小值,所以+1
		if(op==5) printf("%d\n",tr[get_pre(x)].v);
		if(op==6) printf("%d\n",tr[get_suc(x)].v);
	}
	return 0;
}
/*
输入样例:
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
输出样例:
106465
84185
492737
*/
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信