今天有同学去面试,被问到了“跳表”这种数据结构,说实话我之前对它了解不多,于是上网查了跳表的资料,并在这里总结一下。

什么是跳表?要说清楚这个问题,我们就要先从普通的有序链表说起。一个普通有序列表的结构如下:

link list
我们可以看到,上图所示的链表按照由小到大的顺序排列(-1表示最小值,1表示最大值,这是本文的一个约定),如果我们想要查找一个元素x,算法如下:

1
2
3
cell *p = head;
while (p->next->key < x)  p=p->next;
return p;

上面这个算法得到了x元素的前驱或者所有大于x的元素中最小的一个元素。
基于上面这个链表,我们想要插入一个元素35的算法是:

1
2
3
4
5
p = find(35)
cell *p1 = (cell *) malloc(sizeof(cell));
p1->key=35;
p1->next = p->next ;
p->next = p1 ;

想要删除元素37的算法是:

1
2
3
4
p=find(37);
CELL *p1 =p->next;
p->next = p1->next ;
free(p1);

我想这些算法大家都应该是耳熟能详了,对于这样一个链表,查找、删除、插入一个元素的时间复杂度都是O(n)。

*********************我是分割线************************

好,下面我们正式开始介绍跳表。跳表是个概率性数据结构,可以被看作是二叉树的一个变种。跳表是由William Pugh在1990年发明的。它是一种用户维护有序元素的数据结构。

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

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

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

让我们用一个跳表来重新构建文章开头的有序链表:

通过图我们可以看出,整个跳表分为三层,每一层都是一个有序链表,第一层包含所有的元素。top指针指向最高层的-1元素,较高层的元素都能在较低的层里找到,并且较高层的元素含有一个指针指向下一层值相同的元素。

上面的特征和图基本就给出了一个跳表的定义和结构。至于哪些元素应该再更高一层中保留,我们会在下面叙述。

在结构清晰之后,我们需要明白的是跳表为什么要这样设计?这么存储的好处是什么呢?让我们通过对跳表操作来寻找答案。

首先是查找操作。在跳表中查找一个元素x的算法如下:

1
2
3
4
5
6
p=top
While(1){
    while (p->next->key < x ) p=p->next;
    If (p->down == NULL ) return p->next
    p=p->down ;
}

接着是插入算法。假设要插入一个元素“119”,我们设定需要插入该元素的层数为“k”(即我们需要在所有的[1,k]范围内的层里都插入元素。k的值我们会在下文中叙述),则插入算法是:

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
int insert(val x){
 
    int i;
    int j = n; //n是当前表所拥有的level数
 
    cell *p[k]; //指针数组,用来保存每一层要插入元素的前驱
 
    cell *p1;
    p1 = top->next;
 
    while(p1){
        while(p1->next->val < x) p1=p1->next;
        if(j <= k){
            p[j-1] = p1; //保存每一层的指针
            p1 = p1->down; //指向下一层
            j--;
        }
    }
 
    //下面的代码是将x插入到各层
    for (i = 0; i<k; i++){
        if(p[i]==NULL){//k>n的情况,需要创建一个层
            //创建层的第一个元素,并将top指向它
            cell *elementhead = (cell *) malloc(sizeof(cell));
            element->val = -1;
            element->down = top;
            top = elementhead; 
 
            //创建最后一个元素
            cell *elementtail = (cell *) malloc(sizeof(cell));
            elementtail->val = 1;
            elementtail->next = elementtail->down = NULL;
 
            //在该层中创建并插入x
            cell *element = (cell *) malloc(sizeof(cell));
            element->val = x;
            elementhead->next = element;
            element->next = elementtail;
            element->down = p[i-1]->next;
        }
 
        //正常插入一个元素
        cell *element = (cell *) malloc(sizeof(cell));
        element->val = x;
        element->next = p[i]->next;
        element->down = (i=0?NULL:(p[i-1]->next));
        p[i]->next = element;
    }
 
    return 0;
}

最后是删除操作。删除一个元素x,如果x被删除后某层只剩下头尾两个节点,则删除这一层。具体算法如下:

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
int delete(val x){
 
    int i = n; //n表示当前总层数
    cell *p, *p1;
    p = top;
 
    while(n>0){
        while(p->next->val < x) p=p->next;
        if(p->next->val == x){//假如当前层存在节点x,删除
            if(p = top && p->next->next->val == INT_MAX){//该层之存在一个节点
                top = p->down;
                free(p->next->next);
                free(p->next);
                free(p);
                p = top;
            }
            else{
                p1 = p->next;
                p->next = p1->next;
                free(p1);
            }
        }
        p = p->down;
        n--;
    }
}


好了,我们可以看到,无论查找、插入、删除,跳表的时间复杂度都是O(lgn)!这就是为什么我们要引入跳表。

最后,让我们来阐述哪些元素应该在上一层保留,以及插入操作时确定插入元素的层数k。
哪些元素应该在高层保留,是随机决定的。具体算法如下:

  • 我们假定一个函数rand(),随机返回1或者0
  • 假设元素i最多在第k层保留
  • k的值由程式“ while(rand()) k++;”来决定
  • 看明白了么?也就是从第一层随机选出一些元素放到第二层,再从第二层随机选出元素放到第三层,以此类推,知道没有元素再被选出。插入操作时被插入元素的层数也是这么得来的。

    本文参考资料:http://www.kernelchina.org/algorithm/SL.ppt

    anyShare分享到:
              
    Tagged with:
     

    10 Responses to “跳表(Skip List)的介绍以及查找插入删除等操作”

    1. littlebeauty says:

      恩,学习了。。。。。

    2. Thanks for this! I'll check this site everyday and looking for some posts like this.

    3. 老栋 says:

      # 在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
      这个是跳跃表的特征吗?不好吧,万一实际的数据里面出现了-1和1怎么办?我的做法是全部清0表示最小,置1为最大

    4. omelette says:

      if(p = top && p->next->next->val == INT_MAX){//该层之存在一个节点

      方法理解了,只是删除节点的代码有两处bug

    5. 大桂 says:

      在插入元素的时候是不是少了一个else语句?

      //正常插入一个元素
      cell *element = (cell *) malloc(sizeof(cell));
      element->val = x;
      element->next = p[i]->next;
      element->down = (i=0?NULL:(p[i-1]->next));
      p[i]->next = element;
      这一段代码是不是应该放到else语句里面?在下笨拙,如果说得有错,还望博主指出,谢谢...

    6. 吴洪辉 says:

      讲得很好,不过代码就不行了,有多个bug

    7. Lukas says:

      Hello webmaster do you need unlimited content for your page ?
      What if you could copy post from other sites, make it unique and publish on your blog - i know the right tool for you, just search in google:
      Ziakdra's article tool

    8. Hello admin of this blog, do you allow guest posting
      ??? Please let me know, i'm interested .

    Leave a Reply

    Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).