跳表SkipList,顾名思义是链表的一种,或者说它是单链表的变异实现,使用跳表可以将查询操作的复杂度控制到θ(lg N),而普通的链表只能通过顺序查找,复杂度为θ(N),如此跳表的优势就很明显了,虽然它是通过以空间换时间搞定的。

先看一下普通的有序单链表:

oenhan

要在里面查找一个值就需要顺序比较,复杂度大家都清楚了。如何降低复杂度,折半查找也却可以将复杂度降到θ(lg N),但不适应单链表,那就将折半的思想抽出来,隔一段位置就建立一个标签索引,根据标签索引缩短查找范围,就是跳表,如下图:

跳表通过对间隔的数据做一个标签索引,产生了多层单链表,在最高层依次确定查找数据的范围,最终将范围缩小到可接受值,我们看跳表其实就是一个二叉查找树的变形,只是所有的数据都在最左段,其他节点用来建立查找索引,如此跳表的插入删除就比二叉查找树方便多了。

查找过程:

例子:查找元素 117

  1. 比较 21, 比 21 大,往后面找
  2. 比较 37, 比 37大,比链表最大值小,从 37 的下面一层开始找
  3. 比较 71, 比 71 大,比链表最大值小,从 71 的下面一层开始找
  4. 比较 85, 比 85 大,从后面找
  5. 比较 117, 等于 117, 找到了节点。

查找代码:

插入过程:

首先需要确定插入数值的层数K,即数值要建立K-1个索引。K通过随机数random(0,1)掷硬币得出,即为投掷出0的次数

如:

跳表的插入-oenhan

如果插入的值是119,层数为2,则遍历倒数2层,插入相关的数据节点。

具体代码:


跳表SkipList的原理和C实现来自于OenHan

链接为:http://oenhan.com/skiplist-principle

2 对 “跳表SkipList的原理和C实现”的想法;

  1. 插入的算法,找每一层的小于value的节点的迭代,p = p->down;level–;应该在括号外面吧~

zhangyi进行回复 取消回复