跳跃表（skiplist）是一种随机化的数据结构，是一种可以与平衡树媲美的层次化链表结构——查找、删除、添加等操作都可以在对数期望时间下完成，以下是一个典型的跳跃表例子：
到底有多随机，我们看了原理就知道了。
跳跃表原理这里借助(1条消息) 跳跃表的原理和实现（Java）_CoderLucas的博客-CSDN博客_跳跃表原理和实现 中的图来讲解。
查找假设当前我们要查找 39，我们要先从 head (第一层的第一个元素)开始查找：
- 39 > 负无穷，继续往后查找
- 39 > 17，继续往后查找
- 39 < 正无穷，此时找到了第一个大于 39 的数，所以需要往后退一步，即退到最后一个小于等于 39 的数，这样方便下一层的查找. 这里是退到 17，然后跳到第二层的17，开始下一层的查找
然后从第二层开始查找：
- 39 > 17，继续往后查找
- 39 > 25，继续往后查找
- 39 < 55，此时找到了第一个大于 39 的数，同样，退一步，去下一层查找，即从第三层的 25 继续查找
第三层查找：
- 39 > 25，继续往后查找
- 39 > 31，继续往后查找
- 39 < 55，此时找到了第一个大于 39 的数，同样，退一步，去下一层查找，即从第四层的 31 继续查找
第四层查找：
- 39 > 31，继续向后查找
- 39 > 38，继续向后查找
- 39 < 55，此时找到了第一个大于 39 的数，同样，退一步，去下一层查找，即从第四层的 38 继续查找
第五层查找：
插入
- 39 > 38，继续向后查找
- 39 == 39，找到了。
与查找类似，我们需要找到一个合适的插入位置，即找到最后一个小于插入值的节点(或者第一个大于插入值的节点)，然后将新的节点插入。
但是，在看到跳跃表的结构时，大家可能有疑问，跳跃表这么多层是怎么创建出来的？又是何时创建出来的？每一层的节点又是怎么选取的？
在最开始，我们说了这是一种随机化的数据结构，它的随机就体现在这里，在视频 《MIT 算法导论》的第 12 集中，插入一个节点时，我们用抛硬币的方式来决定是否要将该节点往上提。由此，我们明白了何时创建多层链表，以及如何选取节点，还有一个问题是，怎么创建多层链表？
当我们将新插入的节点上提时，还需要再抛一次硬币，来判断是不是还需要将它再上提一层，如此重复，直到抛硬币的结果不再是上提。
如果上一层不存在，则创建一层，每一层都有一个负无穷和正无穷的首尾节点，以便跳跃。
删除删除同样也和查找类似，当我们找到了要删除的节点(可以是最上层，也可以是最下层)，逐层将它们从链表中删除即可，
跳跃表实现 跳跃表节点template跳跃表struct skipEntry { int _key; T _val; skipEntry * _prev; skipEntry * _next; skipEntry * _up; skipEntry * _down; skipEntry(int key = 0, T val = T()) :_key(key) ,_val(val) , _prev(nullptr) , _next(nullptr) , _up(nullptr) , _down(nullptr) {} };
跳跃表数据结构主要含有的属性有：
int _n; // 总元素数量 // 跳跃表首尾节点 skipEntry跳跃表初始化* _head; skipEntry * _tail; unsigned _seed; // 随机种子，生成随机数，判断是否需要将插入节点上升
这里再次借助上面文章的图，来展现一个初始化跳跃表的模型(博主的图画的是真好)：
基本操作 插入因为 head 始终是指向第一层的负无穷节点，所以我们都是从 head 开始查找。如果 key 已经存在，则更新 val，否则执行插入
假设我们现在要在下图中已有的跳跃表中插入 23，首先找到最下层的最后一个小于 23 的节点，然后插入，并判断是否要将其上提。
如果需要上提，则从插入位置开始，向前查找第一个含有上层节点的元素p，然后创建一个新节点，将其插入到上一层。如果没有上一层，则创建一层。
查找与删除查找与删除和上面提到的都差不多，这里就不赘述了。
随机化的方法博主这里使用的是 C++ 的 rand 与 srand 产生随机数，然后判断奇偶来决定是否需要上提，rand 与 srand 的使用读者可以自行查阅，使用很简单。
实现代码博主实现的很简单，只完成了基本的增删改查
#include#include #include // 跳跃表节点 template struct skipEntry { int _key; T _val; skipEntry * _prev; skipEntry * _next; skipEntry * _up; skipEntry * _down; skipEntry(int key = 0, T val = T()) :_key(key) ,_val(val) , _prev(nullptr) , _next(nullptr) , _up(nullptr) , _down(nullptr) {} }; template class skiplist { private: int _n; // 总元素数量 // 跳跃表首尾节点 skipEntry * _head; skipEntry * _tail; unsigned _seed; // 随机种子，生成随机数，判断是否需要将插入节点上升 // 生成随机数 int generateRandomNum() { _seed = time(0); srand(_seed); return rand() % 2; } public: skiplist() :_n(0) ,_head(new skipEntry (INT_MIN)) ,_tail(new skipEntry (INT_MAX)) ,_seed(time(0)) { _head->_next = _tail; _tail->_prev = _head; } private: // 查找，如果找到了返回 key 值，如果没找到返回小于它的前一个节点 skipEntry * _findEntry(int key) { skipEntry * cur = _head; // 从 _head 开始查找 while (1) { // 找到第一个大于 key 的节点 while (key >= cur->_key) { cur = cur->_next; } cur = cur->_prev; // 返回到第一个小于等于 key 的节点 // 判断有没有下一层 if (cur->_down) { cur = cur->_down; continue; } // 返回最后一个小于key的节点 return cur; break; } return nullptr; } public: bool insert(int key, T val) { skipEntry * insertpos = _findEntry(key); if (insertpos->_key == key) // 已存在 { insertpos->_val = val; return true; } skipEntry * newelem = new skipEntry ; if (newelem == nullptr) return false; skipEntry * next = insertpos->_next; newelem->_key = key; newelem->_val = val; newelem->_prev = insertpos; newelem->_next = next; insertpos->_next = newelem; next->_prev = newelem; ++_n; // 判断当前节点是否需要上升 while (generateRandomNum() == 1) // 需要上升 { // 1.找到 newelem 前面第一个含有上升节点的元素 p，如果没有，则创建新的一层 // 2.创建一个与 newelem 相同的节点，连接 newelem 与 该节点，将该节点插到上层 // 3.继续判断是否要上升 // 1.找到 newelem 前面第一个含有上升节点的元素 p，如果没有，则创建新的一层 skipEntry * p = newelem->_prev; while (p && p->_up == nullptr) { p = p->_prev; } if (p == nullptr) // 创建一层 { p = _head; // 需要 INT_MIN, INT_MAX 两个节点作为该层的首尾节点 skipEntry * curLevelHead = new skipEntry (INT_MIN); skipEntry * curLevelTail = new skipEntry (INT_MAX); curLevelHead->_next = curLevelTail; curLevelTail->_prev = curLevelHead; _head->_up = curLevelHead; curLevelHead->_down = _head; _tail->_up = curLevelTail; curLevelTail->_down = _tail; _head = curLevelHead; _tail = curLevelTail; } // 2.创建一个与 newelem 相同的节点，连接 newelem 与 该节点，将该节点插到上层 skipEntry * sameelem = new skipEntry (key, val); sameelem->_down = newelem; newelem->_up = sameelem; p = p->_up; skipEntry * pnext = p->_next; sameelem->_prev = p; p->_next = sameelem; sameelem->_next = pnext; pnext->_prev = sameelem; // 3.继续判断是否要上升 newelem = sameelem; } return true; } bool erase(int key) { // 从下至上删除 skipEntry * cur = _findEntry(key); if (cur->_key != key) return false; while (cur) { cur->_prev->_next = cur->_next; cur->_next->_prev = cur->_prev; skipEntry * up = cur->_up; delete cur; cur = up; } return false; } void* find(int key) { skipEntry * ret = _findEntry(key); return ret->_key == key ? (void*)ret->_val : nullptr; } void clear() { skipEntry * first = _head; skipEntry * last = _tail; while (first->_down) { first = first->_down; } while (last->_down) { last = last->_down; } skipEntry *cur = first->_next; while (cur != last) { erase(cur->_key); cur = cur->_next; } // 删除每一层的首尾元素 while(first) { skipEntry * up = first->_up; delete first; first = up; } while (last) { skipEntry * up = last->_up; delete last; last = up; } } ~skiplist() { clear(); } };
