废话不说，有篇论文可供参考：杨思雨：《伸展树的基本操作与应用》
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
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
|
//Splay的核心操作splay，在每次插入，删除，查找等操作中都要调用，以用来维护树的平衡，具体证明请网上搜索#include <iostream>using
namespace
std;
#define NEW(d) new Splay(d)struct
Splay {
Splay* ch[2];
int
key;
Splay() : key(0) { ch[0] = ch[1] = NULL; }
Splay(int
d) : key(d) { ch[0] = ch[1] = NULL; }
int
cmp(int
d) {
if(key == d) return
-1;
return
key > d ? 0 : 1;
}
}*root = NULL;typedef
Splay* tree;
//左右旋，这里用的技巧是在lrj白书上看到的，旋转不多说，自己理解void
rot(tree& rt, int
d) {
tree k = rt-> ch[d^1]; rt-> ch[d^1] = k-> ch[d]; k-> ch[d] = rt; rt = k;
}void
splay(tree& rt, int
d) {
int
k = rt-> cmp(d);
if(k != -1) {
tree p = rt-> ch[k];
int
k2 = p-> cmp(d);
if(k2 != -1) {
splay(p-> ch[k2], d);
if(k2 == k) rot(rt, k^1);
else
rot(p, k);
}
rot(rt, k^1);
}
}tree max(tree rt){ if(rt == NULL) return
NULL;
tree ret = rt;
while(ret-> ch[1]) ret = ret-> ch[1];
return
ret;
}tree min(tree rt){ if(rt == NULL) return
NULL;
tree ret = rt;
while(ret-> ch[0]) ret = ret-> ch[0];
return
ret;
}tree search(tree rt, int
d) {
tree ret = rt;
while(ret != NULL && ret-> key != d) if(ret-> key > d) ret = ret-> ch[0]; else
ret = ret-> ch[1];
if(ret != NULL) splay(rt, d);
else
return
NULL;
return
rt;
}void
insert(tree& rt, int
d) {
if(rt == NULL) { rt = NEW(d); splay(root, d);}
else
{
int
p = (rt-> key > d ? 0: 1);
insert(rt-> ch[p], d);
}
}void
del(tree& rt, int
d) {
if(search(rt, d) == NULL) return;
tree t;
if(rt-> ch[0] == NULL) t = rt-> ch[1];
else
{
t = rt-> ch[0];
splay(t, max(t)-> key);
t-> ch[1] = rt-> ch[1];
}
delete
rt;
rt = t;
}/*//合并l和r树，前提是r中元素全部大于l的最大元素tree merge(tree l, tree r) { tree m = max();
splay(l, m-> key);
l-> ch[1] = r;
return l;
}//以rt中节点nod分裂rt树为l树和r树，其中nod属于l树void split(tree nod, tree rt, tree& l, tree& r) { splay(rt, nod-> key);
l = rt;
r = rt-> ch[1];
l-> ch[1] = NULL;
}*/void
out(string str) {
cout << str;
}int
main() {
out("1: insert\n2: del\n3: search\n4: max\n5: min\n6: root\n7: Splay\n");
int
c, t;
tree a;
while(cin >> c) {
switch(c) {
case
1: cin >> t;
insert(root, t);
break;
case
2: cin >> t;
del(root, t);
break;
case
3: cin >> t;
if(search(root, t) == NULL) out("Not here\n");
else
out("Is here!\n");
break;
case
4: a = max(root);
if(a != NULL) cout << a-> key << endl;
else
out("Warn!\n");
break;
case
5: a = min(root);
if(a != NULL) cout << a-> key << endl;
else
out("Warn!\n");
break;
case
6: if(root != NULL) { out("root is: "); cout << root-> key << endl; }
else
out("Warn!\n");
break;
case
7: cin >> t;
a = search(root, t);
if(a == NULL) out("Not here\n");
else
splay(root, t);
break;
default:
break;
}
}
return
0;
} |