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
typedef struct node    //每个节点的数据结构
2
{
3
    keyType key;       // key值
4
    valueType value;   // value值
5
 struct node *next[1];  // 后继指针数组，柔性数组 可实现结构体的变长
6
} Node;
7
typedef struct skip_list    //跳表结构
8
{
9
 int level;    // 最大层数
10
    Node *head;   //指向头结点
11
} 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
int randomLevel()
3
{
4
 int level=1;
5
 while (rand()%2)
6
        level++;
7
    level=(MAX_L>level)? level:MAX_L;
8
 return level;
9
}
10
/*
11
step1:查找到在每层待插入位置,跟新update数组
12
step2:需要随机产生一个层数
13
step3:从高层至下插入,与普通链表的插入完全相同。
14
*/
15
bool insert(skip_list *sl, keyType key, valueType val)
16
{
17
    Node *update[MAX_L];
18
    Node *q=NULL,*p=sl->head;//q,p初始化
19
 int i=sl->level-1;
20
 /******************step1*******************/
21
  //从最高层往下查找需要插入的位置,并更新update
22
  //即把降层节点指针保存到update数组
23
 for( ; i>=0; --i)
24
 {
25
 while((q=p->next[i])&& q->key<key)
26
            p=q;
27
        update[i]=p;
28
 }
29
 if(q && q->key == key)//key已经存在的情况下
30
 {
31
        q->value = val;
32
 return true;
33
 }
34
 /******************step2*******************/
35
  //产生一个随机层数level
36
 int level = randomLevel();
37
  //如果新生成的层数比跳表的层数大
38
 if(level>sl->level)
39
 {
40
  //在update数组中将新添加的层指向header
41
 for(i=sl->level; i<level; ++i)
42
 {
43
            update[i]=sl->head;
44
 }
45
        sl->level=level;
46
 }
47
  //printf("%d\n", sizeof(Node)+level*sizeof(Node*));
48
 /******************step3*******************/
49
  //新建一个待插入节点,一层一层插入
50
    q=create_node(level, key, val);
51
 if(!q)
52
 return false;
53
54
  //逐层更新节点的指针,和普通链表插入一样
55
 for(i=level-1; i>=0; --i)
56
 {
57
        q->next[i]=update[i]->next[i];
58
        update[i]->next[i]=q;
59
 }
60
 return true;
61
}

skiplist3

删除节点

1
bool erase(skip_list *sl, keyType key)
2
{
3
    Node *update[MAX_L];
4
    Node *q=NULL, *p=sl->head;
5
 int i = sl->level-1;
6
 for(; i>=0; --i)
7
 {
8
 while((q=p->next[i]) && q->key < key)
9
 {
10
      p=q;
11
 }
12
        update[i]=p;
13
 }
14
  //判断是否为待删除的key
15
 if(!q || (q&&q->key != key))
16
 return false;
17
18
  //逐层删除与普通链表删除一样
19
 for(i=sl->level-1; i>=0; --i)
20
 {
21
 if(update[i]->next[i]==q)//删除节点
22
 {
23
            update[i]->next[i]=q->next[i];
24
  //如果删除的是最高层的节点,则level--
25
 if(sl->head->next[i]==NULL)
26
                sl->level--;
27
 }
28
 }
29
 free(q);
30
  q=NULL;
31
 return true;
32
}

查找操作

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