引言
二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。改造之后的数据结构叫作跳表。
定义
跳表是一个随机化的数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。
跳表是一种可以替代平衡树的数据结构。跳表追求的是概率性平衡，而不是严格平衡。因此，跟平衡二叉树相比，跳表的插入和删除操作要简单得多，执行也更快。
C++简单实现
下面实现过程主要是简单实现跳表的过程，不是多线程安全的，LevelDB实现的跳表支持多线程安全，用了std::atomic原子操作，本文主要是为了理解跳表的原理，所以采用最简单的实现。
|
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#ifndef SKIPLIST_H#define SKIPLIST_H#include <ctime>#include <initializer_list>#include <iostream>#include <random>template <typename Key>class Skiplist {public: struct Node { Node(Key k) : key(k) {} Key key; Node* next[1]; // C语言中的柔性数组技巧 };private: int maxLevel; Node* head; enum { kMaxLevel = 12 };public: Skiplist() : maxLevel(1) { head = newNode(0, kMaxLevel); } Skiplist(std::initializer_list<Key> init) : Skiplist() { for (const Key& k : init) { insert(k); } } ~Skiplist() { Node* pNode = head; Node* delNode; while (nullptr != pNode) { delNode = pNode; pNode = pNode->next[0]; free(delNode); // 对应malloc } } // 禁止拷贝构造和赋值 Skiplist(const Skiplist&) = delete; Skiplist& operator=(const Skiplist&) = delete; Skiplist& operator=(Skiplist&&) = delete;private: Node* newNode(const Key& key, int level) { /* * 开辟sizeof(Node) + sizeof(Node*) * (level - 1)大小的空间 * sizeof(Node*) * (level - 1)大小的空间是给Node.next[1]指针数组用的 * 为什么是level-1而不是level，因为sizeof(Node)已包含一个Node*指针的空间 */ void* node_memory = malloc(sizeof(Node) + sizeof(Node*) * (level - 1)); Node* node = new (node_memory) Node(key); for (int i = 0; i < level; ++i) node->next[i] = nullptr; return node; } /* * 随机函数，范围[1, kMaxLevel]，越小概率越大 */ static int randomLevel() { int level = 1; while (rand() % 2 && level < kMaxLevel) level++; return level; }public: Node* find(const Key& key) { // 从最高层开始查找，每层查找最后一个小于key的前继节点，不断缩小范围 Node* pNode = head; for (int i = maxLevel - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) { pNode = pNode->next[i]; } } // 如果第一层的pNode[0]->key == key，则返回pNode->next[0]，即找到key if (nullptr != pNode->next[0] && pNode->next[0]->key == key) return pNode->next[0]; return nullptr; } void insert(const Key& key) { int level = randomLevel(); Node* new_node = newNode(key, level); Node* prev[kMaxLevel]; Node* pNode = head; // 从最高层开始查找，每层查找最后一个小于key的前继节点 for (int i = level - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) { pNode = pNode->next[i]; } prev[i] = pNode; } // 然后每层将新节点插入到前继节点后面 for (int i = 0; i < level; ++i) { new_node->next[i] = prev[i]->next[i]; prev[i]->next[i] = new_node; } if (maxLevel < level) // 层数大于最大层数，更新最大层数 maxLevel = level; } void erase(const Key& key) { Node* prev[maxLevel]; Node* pNode = head; // 从最高层开始查找，每层查找最后一个小于key的前继节点 for (int i = maxLevel - 1; i >= 0; --i) { while (pNode->next[i] != nullptr && pNode->next[i]->key < key) pNode = pNode->next[i]; prev[i] = pNode; } // 如果找到key， if (pNode->next[0] != nullptr && pNode->next[0]->key == key) { Node *delNode = pNode->next[0]; // 从最高层开始，如果当前层的next节点的值等于key，则删除next节点 for (int i = maxLevel - 1; i >= 0; --i) { if (prev[i]->next[i] != nullptr && key == prev[i]->next[i]->key) prev[i]->next[i] = prev[i]->next[i]->next[i]; } free(delNode); // 最后销毁pNode->next[0]节点 } // 如果max_level>1且头结点的next指针为空，则该层已无数据，max_level减一 while (maxLevel > 1 && head->next[maxLevel] == nullptr) { maxLevel--; } }};#endif |
Redis和LevelDB选用跳表而弃用红黑树的原因
- Skiplist的复杂度和红黑树一样，而且实现起来更简单。
- 在并发环境下Skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。
以上就是c++如何实现跳表的详细内容，更多关于c++ 跳表的资料请关注服务器之家其它相关文章！
原文链接：https://www.cnblogs.com/evenleee/p/13355499.html
