么么达地学习平衡树。不难，看了一个下午后就懂了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;} |
原文：http://www.cnblogs.com/iwtwiioi/p/3536845.html