DragonDreamYF > 普通平衡树之 Splay

普通平衡树之 Splay

2019-08-01

Splay

颓了一个暑假来更新一下blog的蒟蒻

我是在夏令营接触的平衡树 Splay， 在当时并不是很理解， 所以查阅了很多资料， 但并不是很满意， 于是我打算自己写一个Splay入门， 顺便当作一种温习。

前言：毕竟是入门，并且博主也只会入门，所以如有错误，再三见谅，请加QQ提出。

Splay

P3369 【模板】普通平衡树

首先贴个例题，毕竟看着题才容易加深理解。

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
#include <iostream>
#include <cstdio>
using namespace std ;
struct  node {
	int fa ;
	int cnt ;
	int son ;
	int ch[2] ;
	int val ;
}t[500100] ;
int root = 0 ;
int n ;
int tot ;
void push_up (int x) {
	t[x] . son = t[t[x] . ch[1]] . son + t[t[x] . ch[0]] . son + t[x] . cnt ;
}

void rotate (int x) {
	int y = t[x] . fa ;
	int z = t[y] . fa ;
	int k = t[y] . ch[1] == x ;
	t[z] . ch[t[z] . ch[1] == y] = x ;
	t[x] . fa = z ;
	t[y] . ch[k] = t[x] . ch[k ^ 1] ;
	t[t[x] . ch[k ^ 1]] . fa = y ;
	t[x] . ch[k ^ 1] = y ;
	t[y] . fa = x ;
	push_up (y) ;
	push_up (x) ;
}
void Splay (int x, int goal) {
	while (t[x] . fa != goal) {
		int y = t[x] . fa ;
		int z = t[y] . fa ;
		if (z != goal) (t[z] . ch[0] == y) ^ (t[y] . ch[0] == x) ? rotate (x) : rotate (y) ;
		rotate (x) ;
	}
	if (goal == 0) root = x ;
}
void insert (int x) {
	int u = root ;
	int fa = 0 ;
	while (u && t[u] . val != x) {
		fa = u ;
		u = t[u] . ch[x > t[u] . val] ;
	}
	if (u) t[u] . cnt ++ ;
	else {
		u = ++ tot ;
		if (fa) t[fa] . ch[x > t[fa] . val] = u ;
		t[u] . fa = fa ;
		t[u] . val = x ;
		t[u] . ch[0] = 0 ;
		t[u] . ch[1] = 0 ;
		t[u] . son = 1 ;
		t[u] . cnt = 1 ;
	}
	Splay (u, 0) ;
}
void find (int x) {
	int u = root ;
	if (!u) return ;
	while (t[u] . ch[x > t[u] . val] && t[u] . val != x) u = t[u] . ch[x > t[u] . val] ;
	Splay (u, 0) ;
}
int Next (int x, int f) {
	find (x) ;
	int u = root ;
	if ((t[u] . val > x && f) || (t[u] . val < x && !f)) return u ;
	u = t[u] . ch[f] ;
	while (t[u] . ch[f ^ 1]) u = t[u] . ch[f ^ 1] ;
	return u ;
}
void Delete (int x) {
	int last = Next (x, 0) ;
	int next = Next (x, 1) ;
	Splay (last, 0) ;
	Splay (next, last) ;
	int del = t[next] . ch[0] ;
	if (t[del] . cnt > 1) {
		t[del] . cnt -- ;
		Splay (del, 0) ;
	}
	else t[next] . ch[0] = 0 ;
}
int rnk (int x) {
	int u = root ;
	if (t[u] . son < x) return false ;
	while (1) {
		int y = t[u] . ch[0] ;
		if (x > t[y] . son + t[u] . cnt) {
			x -= t[y] . son + t[u] . cnt ;
			u = t[u] . ch[1] ;
		}
		else if (t[y] . son >= x) u = y ;
		else return t[u] . val ;
	}
}
int main() {
	insert (2147483647) ;
	insert (-2147483647) ;
	cin >> n ;
	for (int i = 1; i <= n; i++) {
		int flag, x ;
		cin >> flag ;
		cin >> x ;
		if (flag == 1) {
			insert (x) ;
		}
		if (flag == 2) {
			Delete (x) ;
		}
		if (flag == 3) {
			find (x) ;
			cout << t[t[root] . ch[0]] . son << endl ;
		}
		if (flag == 4) {
			cout << rnk (x + 1) << endl ;
		}
		if (flag == 5) {
			cout << t[Next (x, 0)] . val << endl ;
		}
		if (flag == 6) {
			cout << t[Next (x, 1)] . val << endl ;
		}
	}
	return 0 ;
}

嘛，板子贴出来了，想复制就复制吧，我不拦着。

呐，对了，本题我是靠着yyb大佬的题解撑过来的，如有雷同，那很正常。

读题可知，要解决本题，需要六个操作，然而5，6可以合并，所以是5个主操作，我将逐个为你讲解。

首先，关于结构体的定义。

1
2
3
4
5
6
7
struct  node {
	int fa ;// fa 代表的是他的父亲
	int cnt ;// cnt 代表的是他的个数，也就是说有几个和他相同的数
	int son ;// son 代表的是他儿子的个数
	int ch[2] ;// 代表的是他的左右子节点，即两个儿子，ch[0] 指的是小于他的儿子，ch[1] 代表的是大于他的儿子
	int val ;// val 代表的是当前这个位置的值
}t[500100] ;