SkipList

概述

跳表是个概率性数据结构，可以被看作是二叉树的一个变种。跳表是由William Pugh在1990年发明的。它是一种用户维护有序元素的数据结构。

特征

一个跳表，应该具有以下特征：

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

构造过程

跳表的构造过程是：

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

复杂度

  1. The expected number of levels is O( log n )
    (here n is the numer of elements)
  2. The expected time for insert/delete/find is O( log n )
  3. The expected size (number of cells) is O(n )

复杂度证明

关于时空效率的证明：

空间复杂度 O(n)

对于每层的期待：第一层n，第二层n/2，第三层n/22，…，直到 n/2log n=1。所以，总空间需求：
S = n + n/2 + n/22 + … + n/2log n < n(1 + 1/2 + 1/22 + … + 1/2∞) =2n
因此他的空间复杂度为 2n = O(n)

Skip List高度

对每层来说，它会向上增长的概率为1/2，则第m层向上增长的概率为1/2m；n个元素，则在m层元素数目的期待为Em = n/2m；当Em = 1，m = log2n即为层数的期待。故其高度期待为 Eh = O(log n)。
*关于“高概率（high probability）”的定义：
对于事件A，如果它发生的概率至少为1-cα/nα，其中cα仅取决于α，那么我们称它为高概率。
在牺牲时间和/或空间的情况下，我们可以选择α的值。

  1. 查找的复杂度：
    claim：在高概率的前提下，查找的时间复杂度为O(log n)

  2. 插入的复杂度：
    claim：在高概率的前提下，插入的时间复杂度为O(log n)
    首先通过查找找到要插入的位置：O(log n)
    之后进行插入，同时对每层进行对应的更新（依照概率决定是否向上增长）：o(log n)

  3. 删除的复杂度：
    claim：在高概率的前提下，删除的时间复杂度为O(log n)

实现源码

skiplist.cpp

参考资料

http://www.kernelchina.org/algorithm/SL.ppt
http://epaperpress.com/sortsearch/skl.html
http://www.spongeliu.com/63.html
http://www.cnblogs.com/flyfy1/archive/2011/02/24/1963347.html
http://courses.csail.mit.edu/6.046/spring04/handouts/skiplists.pdf