Skip List(跳跃表)原理详解与实现【转】

时间:2022-02-11 18:56:08

转自:http://dsqiu.iteye.com/blog/1705530

Skip List(跳跃表)原理详解与实现

本文内容框架:

§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定义

像下面这样(初中物理经常这样用,这里我也盗用下):

一个跳表,应该具有以下特征:

  1. 一个跳表应该有几个层(level)组成;
  2. 跳表的第一层包含所有的元素;
  3. 每一层都是一个有序的链表;
  4. 如果元素x出现在第i层,则所有比i小的层都包含x;
  5. 第i层的元素通过一个down指针指向下一层拥有相同值的元素;
  6. 在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
  7. Top指针指向最高层的第一个元素。

构建有序链表

Skip List(跳跃表)原理详解与实现【转】

的一个跳跃表如下:
Skip List(跳跃表)原理详解与实现【转】

Skip List构造步骤:

1、给定一个有序的链表。

2、选择连表中最大和最小的元素,然后从其他元素中按照一定算法(随机)随即选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层。
3、为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素
4、重复2、3步,直到不再能选择出除最大最小元素以外的元素。

§3 Skip List 完整实现

下面来定义跳表的数据结构(基于C)

首先是每个节点的数据结构

  1. typedef  struct nodeStructure
  2. {
  3. int key;
  4. int value;
  5. struct nodeStructure *forward[1];
  6. }nodeStructure;

跳表的结构如下

  1. typedef  struct skiplist
  2. {
  3. int level;
  4. nodeStructure *header;
  5. }skiplist;

下面是跳表的基本操作

首先是节点的创建

  1. nodeStructure* createNode(int level,int key,int value)
  2. {
  3. nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*));
  4. ns->key=key;
  5. ns->value=value;
  6. return ns;
  7. }

列表的初始化

列表的初始化需要初始化头部,并使头部每层(根据事先定义的MAX_LEVEL)指向末尾(NULL)。

  1. skiplist* createSkiplist()
  2. {
  3. skiplist *sl=(skiplist *)malloc(sizeof(skiplist));
  4. sl->level=0;
  5. sl->header=createNode(MAX_LEVEL-1,0,0);
  6. for(int i=0;i<MAX_LEVEL;i++)
  7. {
  8. sl->header->forward[i]=NULL;
  9. }
  10. return sl;
  11. }

插入元素

插入元素的时候元素所占有的层数完全是随机的,通过随机算法产生

  1. int randomLevel()
  2. {
  3. int k=1;
  4. while (rand()%2)
  5. k++;
  6. k=(k<MAX_LEVEL)?k:MAX_LEVEL;
  7. return k;
  8. }

跳表的插入需要三个步骤,第一步需要查找到在每层待插入位置,然后需要随机产生一个层数,最后就是从高层至下插入,插入时算法和普通链表的插入完全相同。

Skip List(跳跃表)原理详解与实现【转】

  1. bool insert(skiplist *sl,int key,int value)
  2. {
  3. nodeStructure *update[MAX_LEVEL];
  4. nodeStructure *p, *q = NULL;
  5. p=sl->header;
  6. int k=sl->level;
  7. //从最高层往下查找需要插入的位置
  8. //填充update
  9. for(int i=k-1; i >= 0; i--){
  10. while((q=p->forward[i])&&(q->key<key))
  11. {
  12. p=q;
  13. }
  14. update[i]=p;
  15. }
  16. //不能插入相同的key
  17. if(q&&q->key==key)
  18. {
  19. return false;
  20. }
  21. //产生一个随机层数K
  22. //新建一个待插入节点q
  23. //一层一层插入
  24. k=randomLevel();
  25. //更新跳表的level
  26. if(k>(sl->level))
  27. {
  28. for(int i=sl->level; i < k; i++){
  29. update[i] = sl->header;
  30. }
  31. sl->level=k;
  32. }
  33. q=createNode(k,key,value);
  34. //逐层更新节点的指针,和普通列表插入一样
  35. for(int i=0;i<k;i++)
  36. {
  37. q->forward[i]=update[i]->forward[i];
  38. update[i]->forward[i]=q;
  39. }
  40. return true;
  41. }

红色区域为辅助数组update的内容

删除节点

删除节点操作和插入差不多,找到每层需要删除的位置,删除时和操作普通链表完全一样。不过需要注意的是,如果该节点的level是最大的,则需要更新跳表的level。

  1. bool deleteSL(skiplist *sl,int key)
  2. {
  3. nodeStructure *update[MAX_LEVEL];
  4. nodeStructure *p,*q=NULL;
  5. p=sl->header;
  6. //从最高层开始搜
  7. int k=sl->level;
  8. for(int i=k-1; i >= 0; i--){
  9. while((q=p->forward[i])&&(q->key<key))
  10. {
  11. p=q;
  12. }
  13. update[i]=p;
  14. }
  15. if(q&&q->key==key)
  16. {
  17. //逐层删除,和普通列表删除一样
  18. for(int i=0; i<sl->level; i++){
  19. if(update[i]->forward[i]==q){
  20. update[i]->forward[i]=q->forward[i];
  21. }
  22. }
  23. free(q);
  24. //如果删除的是最大层的节点,那么需要重新维护跳表的
  25. for(int i=sl->level-1; i >= 0; i--){
  26. if(sl->header->forward[i]==NULL){
  27. sl->level--;
  28. }
  29. }
  30. return true;
  31. }
  32. else
  33. return false;
  34. }

查找

跳表的优点就是查找比普通链表快,当然查找操作已经包含在在插入和删除过程,实现起来比较简单。

Skip List(跳跃表)原理详解与实现【转】

搜索key=14的示意图

  1. int search(skiplist *sl,int key)
  2. {
  3. nodeStructure *p,*q=NULL;
  4. p=sl->header;
  5. //从最高层开始搜
  6. int k=sl->level;
  7. for(int i=k-1; i >= 0; i--){
  8. while((q=p->forward[i])&&(q->key<=key))
  9. {
  10. if(q->key==key)
  11. {
  12. return q->value;
  13. }
  14. p=q;
  15. }
  16. }
  17. return NULL;
  18. }

完整代码如下:

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX_LEVEL 10 //最大层数
  4. //节点
  5. typedef  struct nodeStructure
  6. {
  7. int key;
  8. int value;
  9. struct nodeStructure *forward[1];
  10. }nodeStructure;
  11. //跳表
  12. typedef  struct skiplist
  13. {
  14. int level;
  15. nodeStructure *header;
  16. }skiplist;
  17. //创建节点
  18. nodeStructure* createNode(int level,int key,int value)
  19. {
  20. nodeStructure *ns=(nodeStructure *)malloc(sizeof(nodeStructure)+level*sizeof(nodeStructure*));
  21. ns->key=key;
  22. ns->value=value;
  23. return ns;
  24. }
  25. //初始化跳表
  26. skiplist* createSkiplist()
  27. {
  28. skiplist *sl=(skiplist *)malloc(sizeof(skiplist));
  29. sl->level=0;
  30. sl->header=createNode(MAX_LEVEL-1,0,0);
  31. for(int i=0;i<MAX_LEVEL;i++)
  32. {
  33. sl->header->forward[i]=NULL;
  34. }
  35. return sl;
  36. }
  37. //随机产生层数
  38. int randomLevel()
  39. {
  40. int k=1;
  41. while (rand()%2)
  42. k++;
  43. k=(k<MAX_LEVEL)?k:MAX_LEVEL;
  44. return k;
  45. }
  46. //插入节点
  47. bool insert(skiplist *sl,int key,int value)
  48. {
  49. nodeStructure *update[MAX_LEVEL];
  50. nodeStructure *p, *q = NULL;
  51. p=sl->header;
  52. int k=sl->level;
  53. //从最高层往下查找需要插入的位置
  54. //填充update
  55. for(int i=k-1; i >= 0; i--){
  56. while((q=p->forward[i])&&(q->key<key))
  57. {
  58. p=q;
  59. }
  60. update[i]=p;
  61. }
  62. //不能插入相同的key
  63. if(q&&q->key==key)
  64. {
  65. return false;
  66. }
  67. //产生一个随机层数K
  68. //新建一个待插入节点q
  69. //一层一层插入
  70. k=randomLevel();
  71. //更新跳表的level
  72. if(k>(sl->level))
  73. {
  74. for(int i=sl->level; i < k; i++){
  75. update[i] = sl->header;
  76. }
  77. sl->level=k;
  78. }
  79. q=createNode(k,key,value);
  80. //逐层更新节点的指针,和普通列表插入一样
  81. for(int i=0;i<k;i++)
  82. {
  83. q->forward[i]=update[i]->forward[i];
  84. update[i]->forward[i]=q;
  85. }
  86. return true;
  87. }
  88. //搜索指定key的value
  89. int search(skiplist *sl,int key)
  90. {
  91. nodeStructure *p,*q=NULL;
  92. p=sl->header;
  93. //从最高层开始搜
  94. int k=sl->level;
  95. for(int i=k-1; i >= 0; i--){
  96. while((q=p->forward[i])&&(q->key<=key))
  97. {
  98. if(q->key == key)
  99. {
  100. return q->value;
  101. }
  102. p=q;
  103. }
  104. }
  105. return NULL;
  106. }
  107. //删除指定的key
  108. bool deleteSL(skiplist *sl,int key)
  109. {
  110. nodeStructure *update[MAX_LEVEL];
  111. nodeStructure *p,*q=NULL;
  112. p=sl->header;
  113. //从最高层开始搜
  114. int k=sl->level;
  115. for(int i=k-1; i >= 0; i--){
  116. while((q=p->forward[i])&&(q->key<key))
  117. {
  118. p=q;
  119. }
  120. update[i]=p;
  121. }
  122. if(q&&q->key==key)
  123. {
  124. //逐层删除,和普通列表删除一样
  125. for(int i=0; i<sl->level; i++){
  126. if(update[i]->forward[i]==q){
  127. update[i]->forward[i]=q->forward[i];
  128. }
  129. }
  130. free(q);
  131. //如果删除的是最大层的节点,那么需要重新维护跳表的
  132. for(int i=sl->level - 1; i >= 0; i--){
  133. if(sl->header->forward[i]==NULL){
  134. sl->level--;
  135. }
  136. }
  137. return true;
  138. }
  139. else
  140. return false;
  141. }
  142. void printSL(skiplist *sl)
  143. {
  144. //从最高层开始打印
  145. nodeStructure *p,*q=NULL;
  146. //从最高层开始搜
  147. int k=sl->level;
  148. for(int i=k-1; i >= 0; i--)
  149. {
  150. p=sl->header;
  151. while(q=p->forward[i])
  152. {
  153. printf("%d -> ",p->value);
  154. p=q;
  155. }
  156. printf("\n");
  157. }
  158. printf("\n");
  159. }
  160. int main()
  161. {
  162. skiplist *sl=createSkiplist();
  163. for(int i=1;i<=19;i++)
  164. {
  165. insert(sl,i,i*2);
  166. }
  167. printSL(sl);
  168. //搜索
  169. int i=search(sl,4);
  170. printf("i=%d\n",i);
  171. //删除
  172. bool b=deleteSL(sl,4);
  173. if(b)
  174. printf("删除成功\n");
  175. printSL(sl);
  176. system("pause");
  177. return 0;
  178. }

§4 Skip List 概率分析

Skip List(跳跃表)原理详解与实现【转】

Skip List(跳跃表)原理详解与实现【转】
 
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