跳表

编程领域术语

增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

简介

跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。

它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。

采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。

原理

跳表的原理非常简单，跳表其实就是一种可以进行二分查找的有序链表。跳表的数据结构模型如图1:

可以看到，跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。

理想情况

在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需进行n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。

实例

图2中c所示的结构为跳表（skiplist）。在该结构中有一组有层次的链。0级链是包含所有元素的有序链表，1级链是0级链的一个子集。i级链所包含的元素是i-1级链的子集。图2c中，i级链上所有的元素均在i-1级链上。

如图2的有序链表中有七个元素。该链表有一个头节点和一个尾节点。节点中的数是该节点的值。对该链表的搜索可能要进行七次比较。可以采用图2b中的办法，把最坏情况下的比较次数减少为四次。搜索一个元素时，首先将它与中间元素进行比较，然后根据得到的结果，或者与链的左半部比较或者与右半部比较。例如如果要找值为26的元素，只需查找40左边的元素。如果要查找值为75的元素，那么只对40以后的元素进行搜索即可。

也可以向图2c中一样，分别在链表左半部分和右半部分的中间节点再增加一个指针，以便进一步减少最坏情况下的搜索比较次数。在图2中有三条链。0级链就是图2a中的初始链，包括了所有七个元素。一级链包括第二，六个元素，而2级链只包括第四个元素。为了寻找值为30的元素，首先与中间元素比较。在2级链中寻找元素所需要的时间为(1)。由于30<40，因此要搜索该链左半部分的中间元素。采用1级链进行搜索所花费的时间为(1)。又因为30>24，故需在0级链中继续进行查找，把该元素与链中下一个元素进行比较。

考察另一个例子。设要查找的元素值为77。首先与40比较，70>40，则在1级链中与75比较。由于77>75，因此在0级链中与75后面的80比较。这时可以得知77不在此字典中。采用图2c中的3级链结构，对所有的搜索至多需三次比较。3级链结构允许在有序链表中进行折半搜索。

通常0级链包括n个元素，1级链包括n/2个元素，2级链包括n/4个元素，而每2i个元素有一个i级链指针。当且仅当一个元素在0～i级链上，但不在i+1级（若该链存在）链上时，我们就说该元素是i级链元素。在图2c中，40是2级链上唯一的元素而75是1级链元素。20、30、60、80是0级链元素。

级的分配

在级基本的分配过程中，可以观察到，在一般跳表结构中，i-1级链中的元素属于i级链的概率为p。假设有一随机数产生器所产生的数在0到RANDMAX间。则下一次所产生的随机数小于等于CutOff=p*RANDMAX的概率为p。因此，若下一随机数小于等于CutOff，则新元素应在1级链上。现在继续确定新元素是否在2级链上，这由下一个随机数来决定。若新的随机数小于等于CutOff，则该元素也属于2级链。重复这个过程，直到得到一随机数大于CutOff为止。故可以用下面的代码为要插入的元素分配级。

intlev=0;

while(rand()<=CutOff) lev++;

这种方法潜在的缺点是可能为某些元素分配特别大的级，从而导致一些元素的级远远超过log1/pN，其中N为字典中预期的最大数目。为避免这种情况，可以设定一个上限lev。在有N个元素的跳表中，级MaxLevel的最大值为

可以采用此值作为上限。

另一个缺点是即使采用上面所给出的上限，但还可能存在下面的情况，如在插入一个新元素前有三条链，而在插入之后就有了10条链。这时，新插入元素的为9级，尽管在前面插入中没有出现3到8级的元素。也就是说，在此插入前并未插入3，4，⋯，8级元素。既然这些空级没有直接的好处，那么可以把新元素的级调整为3。

性能分析

时间复杂性

当跳表中有n个元素时，搜索、插入、删除操作的复杂性均为O(n+MaxLevel)。在最坏情况下，可能只有一个MaxLevel级元素，且余下的所有元素均在0级链上。i>0时，在i级链上花费的时间为(MaxLevel)，而在0级链上花费的时间为O(n)。尽管最坏情况下的性能较差，但跳表仍不失为一种有价值的数据描述方法。其每种操作(搜索、插入、删除)的平均复杂性均为O(logn)，

空间复杂性

至于空间复杂性，注意到最坏情况下所有元素都可能是MaxLevel级，每个元素都需要

MaxLevel+1个指针。因此，除了存储n个元素(也就是n*sizeof(element))，还需要存储链指针（所需空间为O(n*MaxLevel)）。不过，一般情况下，只有n*p个元素在1级链上，n*p2个元素在2级链上，n*pi在i级链上。因此指针域的平均值(不包括头尾节点的指针)是n/(1-p)。因此虽然最坏情况下空间需求比较大，但平均的空间需求并不大。当p=0.5时，平均空间需求(加上n个节点中的指针)大约是2n个指针的空间。

跳表的实现

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省