Skip List（跳跃表）原理详解与实现
转载：http://dsqiu.iteye.com/blog/1705530
本文内容框架：
§1 Skip List 介绍
§2 Skip List 定义以及构造步骤
§3 Skip List 完整实现
§4 Skip List 概率分析
§5 小结
§1 Skip List 介绍
Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。
§2 Skip List 定义以及构造步骤
Skip List定义
像下面这样（初中物理经常这样用，这里我也盗用下）：
一个跳表，应该具有以下特征：
一个跳表应该有几个层（level）组成； 跳表的第一层包含所有的元素； 每一层都是一个有序的链表； 如果元素x出现在第i层，则所有比i小的层都包含x； 第i层的元素通过一个down指针指向下一层拥有相同值的元素； 在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)； Top指针指向最高层的第一个元素。构建有序链表
的一个跳跃表如下：
Skip List构造步骤：
1、给定一个有序的链表。
2、选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层。 3、为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素 4、重复2、3步，直到不再能选择出除最大最小元素以外的元素。
§3 Skip List 完整实现
下面来定义跳表的数据结构（基于C）
列表的初始化需要初始化头部，并使头部每层（根据事先定义的MAX_LEVEL）指向末尾（NULL）。
C代码 skiplist* createSkiplist() { skiplist *sl=(skiplist *)malloc(sizeof(skiplist)); sl->level=0; sl->header=createNode(MAX_LEVEL-1,0,0); for(int i=0;i<MAX_LEVEL;i++) { sl->header->forward[i]=NULL; } return sl; }插入元素的时候元素所占有的层数完全是随机的，通过随机算法产生
C代码 int randomLevel() { int k=1; while (rand()%2) k++; k=(k<MAX_LEVEL)?k:MAX_LEVEL; return k; }
跳表的插入需要三个步骤，第一步需要查找到在每层待插入位置，然后需要随机产生一个层数，最后就是从高层至下插入，插入时算法和普通链表的插入完全相同。
C代码 bool insert(skiplist *sl,int key,int value) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p, *q = NULL; p=sl->header; 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; } //产生一个随机层数K //新建一个待插入节点q //一层一层插入 k=randomLevel(); //更新跳表的level if(k>(sl->level)) { for(int i=sl->level; i < k; i++){ update[i] = sl->header; } sl->level=k; } q=createNode(k,key,value); //逐层更新节点的指针，和普通列表插入一样 for(int i=0;i<k;i++) { q->forward[i]=update[i]->forward[i]; update[i]->forward[i]=q; } return true; }
红色区域为辅助数组update的内容
删除节点操作和插入差不多，找到每层需要删除的位置，删除时和操作普通链表完全一样。不过需要注意的是，如果该节点的level是最大的，则需要更新跳表的level。
C代码 bool deleteSL(skiplist *sl,int key) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 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->header->forward[i]==NULL){ sl->level--; } } return true; } else return false; }
跳表的优点就是查找比普通链表快，当然查找操作已经包含在在插入和删除过程，实现起来比较简单。
搜索key=14的示意图
C代码 int search(skiplist *sl,int key) { nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<=key)) { if(q->key==key) { return q->value; } p=q; } } return NULL; }
完整代码如下：
C代码 #include<stdio.h> #include<stdlib.h> #define MAX_LEVEL 10 //最大层数 //节点 typedef struct nodeStructure { int key; int value; struct nodeStructure *forward[1]; }nodeStructure; //跳表 typedef struct skiplist { int level; nodeStructure *header; }skiplist; //创建节点 nodeStructure* createNode(int level,int key,int value) { nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*)); ns->key=key; ns->value=value; return ns; } //初始化跳表 skiplist* createSkiplist() { skiplist *sl=(skiplist *)malloc(sizeof(skiplist)); sl->level=0; sl->header=createNode(MAX_LEVEL-1,0,0); for(int i=0;i<MAX_LEVEL;i++) { sl->header->forward[i]=NULL; } return sl; } //随机产生层数 int randomLevel() { int k=1; while (rand()%2) k++; k=(k<MAX_LEVEL)?k:MAX_LEVEL; return k; } //插入节点 bool insert(skiplist *sl,int key,int value) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p, *q = NULL; p=sl->header; 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; } //产生一个随机层数K //新建一个待插入节点q //一层一层插入 k=randomLevel(); //更新跳表的level if(k>(sl->level)) { for(int i=sl->level; i < k; i++){ update[i] = sl->header; } sl->level=k; } q=createNode(k,key,value); //逐层更新节点的指针，和普通列表插入一样 for(int i=0;i<k;i++) { q->forward[i]=update[i]->forward[i]; update[i]->forward[i]=q; } return true; } //搜索指定key的value int search(skiplist *sl,int key) { nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--){ while((q=p->forward[i])&&(q->key<=key)) { if(q->key == key) { return q->value; } p=q; } } return NULL; } //删除指定的key bool deleteSL(skiplist *sl,int key) { nodeStructure *update[MAX_LEVEL]; nodeStructure *p,*q=NULL; p=sl->header; //从最高层开始搜 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->header->forward[i]==NULL){ sl->level--; } } return true; } else return false; } void printSL(skiplist *sl) { //从最高层开始打印 nodeStructure *p,*q=NULL; //从最高层开始搜 int k=sl->level; for(int i=k-1; i >= 0; i--) { p=sl->header; while(q=p->forward[i]) { printf("%d -> ",p->value); p=q; } printf("\n"); } printf("\n"); } int main() { skiplist *sl=createSkiplist(); for(int i=1;i<=19;i++) { insert(sl,i,i*2); } printSL(sl); //搜索 int i=search(sl,4); printf("i=%d\n",i); //删除 bool b=deleteSL(sl,4); if(b) printf("删除成功\n"); printSL(sl); system("pause"); return 0; }
§4 Skip List 概率分析
§5 小结
本篇博文已经详细讲解了Skip List数据结构的所有内容，应该可以有一个深入的了解。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。
参考：
①Skip List: http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_skl.htm
②Songeliu: http://www.spongeliu.com/63.html
③Shi Kai Lun ： http://yilee.info/skip-list.html
④Michael T. Goodrich Roberto Tamassia Algorithm Design Foundations, Analysis, and Internet Examples
⑤http://epaperpress.com/sortsearch/skl.html
