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
| struct Node {
Node(int i, Node *r, Node *d) : val(i), right(r), down(d) {}
int val;
Node *right;
Node *down;
};
class Skiplist {
public:
Skiplist() {}
bool search(int target) {
auto cur = head;
while (cur) {
while (cur->right && cur->right->val < target) {
cur = cur->right;
}
if (cur->right && cur->right->val == target) {
return true;
}
cur = cur->down;
}
return false;
}
void add(int num) {
int r_level = 1;
while (r_level <= max_level && (rand() & 1 == 0)) {
++r_level;
}
if (r_level > max_level) {
max_level = r_level;
head = new Node(num, nullptr, head);
}
Node *cur = head;
Node *last = nullptr;
for (int l = max_level; l >= 1; --l) {
while (cur->right && cur->right->val < num) {
cur = cur->right;
}
if (l <= r_level) {
cur->right = new Node(num, cur->right, nullptr);
if (last) {
last->down = cur->right;
}
last = cur->right;
}
cur = cur->down;
}
}
bool erase(int num) {
auto cur = head;
bool seen = false;
for (int l = max_level; l >= 1; --l) {
while (cur->right && cur->right->val < num) {
cur = cur->right;
}
if (cur->right && cur->right->val == num) {
seen = true;
Node *temp = cur->right;
cur->right = cur->right->right;
delete temp;
}
cur = cur->down;
}
return seen;
}
private:
int max_level = 0;
Node *head = nullptr;
};
|