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
| struct SkiplistNode{
int val;
vector<SkiplistNode*> forward;
SkiplistNode(int val,int MAX_LEVEL):val(val),forward(MAX_LEVEL,nullptr){}
};
class Skiplist {
private:
static constexpr const int MAX_LEVEL = 32;
static constexpr const int P = 4;
static constexpr const int S = 0xFFFF;
static constexpr const int PS = S/P;
static constexpr const int INVALID = INT_MAX;
SkiplistNode *dummy_head;
int level;
public:
Skiplist():level(1) {
dummy_head = new SkiplistNode(INVALID,MAX_LEVEL);
}
bool search(int target) {
SkiplistNode * curr = dummy_head;
for(int i=level-1;i>=0;i--){
while(curr->forward[i]&&curr->forward[i]->val<target){
curr=curr->forward[i];
}
}
curr=curr->forward[0];
if(curr&&curr->val==target){
return true;
}
return false;
}
void add(int num) {
int lv=randomLevel();
vector<SkiplistNode*> update(lv,nullptr);
SkiplistNode *curr = dummy_head;
for(int i=level-1;i>=0;i--){
while(curr->forward[i]&&curr->forward[i]->val<num){
curr=curr->forward[i];
}
if(i<lv){
update[i]=curr;
}
}
SkiplistNode *node = new SkiplistNode(num,lv);
for(int i=0;i<min(level,lv);i++){
node->forward[i] = update[i]->forward[i];
update[i]->forward[i]=node;
}
level=max(level,lv);
}
bool erase(int num) {
vector<SkiplistNode*> update(MAX_LEVEL,nullptr);
SkiplistNode *curr = dummy_head;
for(int i=level-1;i>=0;i--){
while(curr->forward[i]&&curr->forward[i]->val<num){
curr=curr->forward[i];
}
update[i]=curr;
}
if(curr->forward[0]==nullptr||curr->forward[0]->val!=num){
return false;
}
curr=curr->forward[0];
for(int i=0;i<curr->forward.size();i++){
update[i]->forward[i]=curr->forward[i];
}
delete curr;
return true;
}
int randomLevel(){
int lv=1;
while(rand()%S<PS){++lv;}
return min(lv,MAX_LEVEL);
}
};
|
