么么达地学习平衡树。不难，看了一个下午后就懂了treap。首先放上treap的代码：
|
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
|
#include <iostream>#include <ctime>#include <cstdlib>using
namespace
std;
#define NEW(d) new treap(d)struct
treap {
treap* ch[2];
int
key, s;
treap() : key(0), s(rand()) { ch[0] = ch[1] = NULL; }
treap(int
d) : key(d), s(rand()) { ch[0] = ch[1] = NULL; }
bool
operator< (const
treap& a) { return
s < a.s ? 1 : 0; }
int
cmp(int
d) {
if(key == d) return
-1;
return
key > d ? 0 : 1;
}
}*root = NULL;typedef
treap* 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
insert(tree& rt, int
d) {
if(rt == NULL) rt = NEW(d);
else
{
int
p = (rt-> key > d ? 0: 1);
insert(rt-> ch[p], d);
if(rt < rt-> ch[d]) rot(rt, p^1); //先插入再旋转
}
}void
del(tree& rt, int
d) {
if(rt == NULL) return;
int
c = rt-> cmp(d);
//如果找到节点
if(c == -1) {
//如果有左右子女
if(rt-> ch[0] != NULL && rt-> ch[1] != NULL) {
int
p = (rt-> ch[1] < rt-> ch[0] ? 1 : 0);
rot(rt, p); del(rt-> ch[p], d);
}
//如果没有子女或只有一个子女
else
{
tree t = rt;
if(rt-> ch[0] == NULL) rt = rt-> ch[1]; else
rt = rt-> ch[0];
delete
t;
}
}
//如果没找到节点
else
del(rt-> ch[c], d);
}tree search(int
d) {
if(root == NULL) return
root;
tree ret = root; int
c = ret-> cmp(d);
while(ret != NULL && c != -1) ret = ret-> ch[c], c = ret-> cmp(d);
return
ret;
}tree max(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> ch[1]) ret = ret-> ch[1];
return
ret;
}tree min(){ if(root == NULL) return
NULL;
tree ret = root;
while(ret-> ch[0]) ret = ret-> ch[0];
return
ret;
}void
out(string str) {
cout << str;
}int
main() {
out("1: insert\n2: del\n3: search\n4: max\n5: min\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(t) == NULL) out("Not here\n");
else
out("Is here!\n");
break;
case
4: a = max();
if(a != NULL) cout << a-> key << endl;
else
out("Warn!\n");
break;
case
5: a = min();
if(a != NULL) cout << a-> key << endl;
else
out("Warn!\n");
break;
default:
break;
}
}
return
0;
} |