一、为什么选择跳表？
目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？
很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。
用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上=下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
二、定义
如果你要在一个有序的序列中查找元素 k ，相信大多数人第一反应都是二分查找。
如果你需要维护一个支持插入操作的有序表，大家又会想到链表。
简单的说，要达到以logn的速度查找链表中的元素
我们先来看看这张图：
如果要在这里面找 21 ，过程为 3→ 6 → 7 → 9 → 12 → 17 → 19 → 21 。
我们考虑从中抽出一些节点，建立一层索引作用的链表：
跳表的主要思想就是这样逐渐建立索引，加速查找与插入。
一般来说，如果要做到严格 O(logn) ，上层结点个数应是下层结点个数的 1/2 。但是这样实现会把代码变得十分复杂，就失去了它在 OI 中使用的意义。
此外，我们在实现时，一般在插入时就确定数值的层数，而且层数不能简单的用随机数，而是以1/2的概率增加层数。
用实验中丢硬币的次数 K 作为元素占有的层数。显然随机变量 K 满足参数为 p = 1/2 的几何分布，K 的期望值 E[K] = 1/p = 2. 就是说，各个元素的层数，期望值是 2 层。
同时，为了防止出现极端情况，设计一个最大层数MAX_LEVEL。如果使用非指针版，定义这样一个常量会方便许多，更能节省空间。如果是指针版，可以不加限制地任由它增长。
inline int rand_level() { int ret = 1; while (rand() % 2 && ret <= MAX_LEVEL) ++ret; return ret; }
我们来看看存储结点的结构体：
struct node { int key; int next[MAX_LEVEL + 1]; } sl[maxn + 10];
next[i] 表示这个结点在第 i 层的下一个结点编号。
分配新结点
为了充分地利用空间，就是用一个栈或是队列保存已经被删除的节点，模拟一个内存池，记录可以使用的内存单元。
可以节省很多空间，使空间在 O(n * MAX_LEVEL) 级
inline void new_node(int &p, int key) { if (top) p = st[top--]; else p = ++node_tot; sl[p].key = key; }
回收结点
其实就是维护内存池，讲腾出的空间记录下来，给下一个插入的节点使用
inline void free_node(int p) { st[++top] = p; }
初始化
按照定义，链表头尾应分别为负与正无穷。但是有时候是不需要的，不过为避免某些锅还是打上的好
inline void init() { new_node(head, -INF), new_node(tail, INF); for (register int i = 1; i <= MAX_LEVEL; ++i) sl[head].next[i] = tail; }
查找
从最上层开始，如果key小于或等于当层后继节点的key,则平移一位；如果key更大，则层数减1，继续比较。最终一定会到第一层（想想为什么）
查找 117
插入
先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）。
然后在 Level 1 … Level K 各个层的链表都插入元素。
用Update数组记录插入位置，同样从顶层开始，逐层找到每层需要插入的位置，再生成层数并插入。
例子：插入 119， K = 2
void insert(int key) { int p = head; int update[MAX_LEVEL + 5]; int k = rand_level(); for (register int i = MAX_LEVEL; i; --i) { while (sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key) p = sl[p].next[i]; update[i] = p; } int temp; new_node(temp, key); for (register int i = k; i; --i) { sl[temp].next[i] = sl[update[i]].next[i]; sl[update[i]].next[i] = temp; } }
删除
与插入类似
void erase(int key) { int p = head; int update[MAX_LEVEL + 5]; for (register int i = MAX_LEVEL; i; --i) { while (sl[p].next[i] ^ tail && sl[sl[p].next[i]].key < key) p = sl[p].next[i]; update[i] = p; } free_node(sl[p].next[1]); for (register int i = MAX_LEVEL; i; --i) { if (sl[sl[update[i]].next[i]].key == key) sl[update[i]].next[i] = sl[sl[update[i]].next[i]].next[i]; } }
三、全部代码示例
/************************************************************************* > File Name: skiplist.c > Author: 杨永利 > Mail: 1795018360@qq.com > Created Time: 2020年10月24日 星期六 07时57分57秒 ************************************************************************/ #include <stdio.h> #include <stdlib.h> #define LEVEL_MAX_LEN 10 #define true 1 #define false 2 typedef char bool; // 跳跃表节点结构体 typedef struct SkipListNode { int key; int data; struct SkipListNode *forward[1]; }SkipListNode; //跳跃表链表结构 typedef struct SkipList { int level; struct SkipListNode *head; }SkipList; //节点初始化 SkipListNode *CreatSkipNode(int level, int key, int data) { SkipListNode *newNode = (SkipListNode *)malloc(sizeof(SkipListNode) + level * sizeof(SkipListNode)); if (newNode == NULL) return NULL; newNode->key = key; newNode->data = data; return newNode; } //初始化跳表 SkipList *CreatSkipList() { SkipList *newlist = (SkipList *)malloc(sizeof(SkipList)); if (newlist == NULL) return NULL; newlist->head = CreatSkipNode(LEVEL_MAX_LEN - 1, 0, 0); for (int i = LEVEL_MAX_LEN - 1; i >= 0; i--) { newlist->head->forward[i] = NULL; } return newlist; } //随机产生层数 int RandLevel() { int k = 1; while (rand() % 2) k++; return (k < LEVEL_MAX_LEN) ? k : LEVEL_MAX_LEN; } //插入节点 bool InsertNode(SkipList *sl, int key, int data) { SkipListNode *update[LEVEL_MAX_LEN]; SkipListNode *p, *q = NULL; p = sl->head; int k = sl->level; //从高到低找节点插入的位置，update存储每一层应该插入的位置 for (int i = k - 1; i >= 0; i--) { while ((q = p->forward[i]) && (q->key < key)) { p = q; } update[i] = p; } //不能插入相同的key if (q && q->key == key) { return false; } //产生一个随机层数 //新建一个待插入节点q，层层插入 k = RandLevel(); //更新跳跃表的level if (k > (sl->level)) { for (int i = (sl->level); i < k; ++i) { update[i] = sl->head; } sl->level = k; } q = CreatSkipNode(k, key, data); //逐层更新节点的指针，跟普通链表的插入一样 for (int i = 0; i < k; ++i) { q->forward[i] = update[i]->forward[i]; update[i]->forward[i] = q; } return true; } //搜索指定的key int SearchByKey(SkipList *sl, int key) { SkipListNode *p, *q = NULL; int k = sl->level; p = sl->head; for (int i = k - 1; i >= 0; i--) { while ((q = p->forward[i]) && (q->key <= key)) { if (q->key == key) return (q->key); p = q; } } return 0; } //删除指定的key bool deleteNode(SkipList *sl, int key) { SkipListNode *p, *q = NULL; SkipListNode *update[LEVEL_MAX_LEN]; p = sl->head; int k = sl->level; for (int i = k - 1; i >= 0; i--) { while ((q = p->forward[i]) && (q->key < key)) { p = q; } update[i] = p; } if (q && q->key == key) { //逐层删除，和删除普通链表一样 for (int i = 0; i < sl->level; ++i) { if (update[i]->forward[i] == q) { update[i]->forward[i] = q->forward[i]; } } free(q); //如果删除的是最大层的节点，那末需要重新维护跳表 for (int i = sl->level - 1; i >= 0; i--) { if (sl->head->forward[i] == NULL) { sl->level--; } } return true; } else { return false; } } //打印跳跃表 void PrintSkipList(SkipList *sl) { SkipListNode *p, *q = NULL; //从最高层开始打印 int k = sl->level; for (int i = k - 1; i >= 0; i--) { p = sl->head; while (q = p->forward[i]) { printf("%d->", p->data); p = q; } printf("\n"); } printf("\n"); } int main(int argc, char* argv[]){ SkipList *sl=CreatSkipList(); for(int i=0;i<=19;i++) { InsertNode(sl,i,i*2); } PrintSkipList(sl); int m=SearchByKey(sl,4); printf("找到的结果为：%d\n",m); bool b = deleteNode(sl, 4); if (b) { printf("删除成功\n"); } PrintSkipList(sl); system("pause"); return 0; }
