Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
–William Pugh

装在整理至:

跳表是由William Pugh发明的，上面的引言就是他给出的解释。跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。

skliplist1

跳跃表结构体

1
2
3
4
5
6
7
8
9
10
11
typedef struct node    //每个节点的数据结构
{
    keyType key;       // key值
    valueType value;   // value值
 struct node *next[1];  // 后继指针数组，柔性数组 可实现结构体的变长
} Node;
typedef struct skip_list    //跳表结构
{
 int level;    // 最大层数
    Node *head;   //指向头结点
} skip_list;

柔性数组

sizeof(Node*)))柔性数组既数组大小待定的数组， C语言中结构体的最后一个元素可以是大小未知的数组，也就是所谓的0长度，所以我们可以用结构体来创建柔性数组。柔性数组既数组大小待定的数组， C语言中结构体的最后一个元素可以是大小未知的数组，也就是所谓的0长度，所以我们可以用结构体来创建柔性数组。

1
#define new_node(n) ((Node*)malloc(sizeof(Node)+n

跳跃表的插入

跳表的插入总结起来需要三步:

  1. 查找到待插入位置, 每层跟新update数组;
  2. 需要随机产生一个层数;
  3. 从高层至下插入,与普通链表的插入完全相同;

skiplist2

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
//插入元素的时候元素所占有的层数完全是随机算法
int randomLevel()
{
 int level=1;
 while (rand()%2)
        level++;
    level=(MAX_L>level)? level:MAX_L;
 return level;
}
/*
step1:查找到在每层待插入位置,跟新update数组
step2:需要随机产生一个层数
step3:从高层至下插入,与普通链表的插入完全相同。
*/
bool insert(skip_list *sl, keyType key, valueType val)
{
    Node *update[MAX_L];
    Node *q=NULL,*p=sl->head;//q,p初始化
 int i=sl->level-1;
 /******************step1*******************/
  //从最高层往下查找需要插入的位置,并更新update
  //即把降层节点指针保存到update数组
 for( ; i>=0; --i)
 {
 while((q=p->next[i])&& q->key<key)
            p=q;
        update[i]=p;
 }
 if(q && q->key == key)//key已经存在的情况下
 {
        q->value = val;
 return true;
 }
 /******************step2*******************/
  //产生一个随机层数level
 int level = randomLevel();
  //如果新生成的层数比跳表的层数大
 if(level>sl->level)
 {
  //在update数组中将新添加的层指向header
 for(i=sl->level; i<level; ++i)
 {
            update[i]=sl->head;
 }
        sl->level=level;
 }
  //printf("%d\n", sizeof(Node)+level*sizeof(Node*));
 /******************step3*******************/
  //新建一个待插入节点,一层一层插入
    q=create_node(level, key, val);
 if(!q)
 return false;

  //逐层更新节点的指针,和普通链表插入一样
 for(i=level-1; i>=0; --i)
 {
        q->next[i]=update[i]->next[i];
        update[i]->next[i]=q;
 }
 return true;
}

skiplist3

删除节点

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
bool erase(skip_list *sl, keyType key)
{
    Node *update[MAX_L];
    Node *q=NULL, *p=sl->head;
 int i = sl->level-1;
 for(; i>=0; --i)
 {
 while((q=p->next[i]) && q->key < key)
 {
      p=q;
 }
        update[i]=p;
 }
  //判断是否为待删除的key
 if(!q || (q&&q->key != key))
 return false;

  //逐层删除与普通链表删除一样
 for(i=sl->level-1; i>=0; --i)
 {
 if(update[i]->next[i]==q)//删除节点
 {
            update[i]->next[i]=q->next[i];
  //如果删除的是最高层的节点,则level--
 if(sl->head->next[i]==NULL)
                sl->level--;
 }
 }
 free(q);
  q=NULL;
 return true;
}

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
valueType *search(skip_list *sl, keyType key)
{
    Node *q,*p=sl->head;
  q=NULL;
 int i=sl->level-1;
 for(; i>=0; --i)
 {
 while((q=p->next[i]) && q->key<key)
 {
            p=q;
 }
 if(q && key==q->key)
 return &(q->value);
 }
 return NULL;
}