Posted 2019-09-01编程 / 数据结构9 minutes read (About 1340 words)

跳表（skiplist）

跳表是一种基于并联的链表，底层是一个普通的有序链表，更高层链表是基于随机方式构建的稀疏子链表，充当下层链表的快速通道，因此链表的长度由低到高层层递减。

跳表的查找、插入和删除操作的平均时间复杂度都为O(logn)，有效地解决有序链表查询效率低下的问题。

注意：跳表的最底层必须是一个有序链表。

构建一个跳表可分以下4个步骤：

给定一个有序的链表作为底层。
构建上一层链表：
1. 选出当前层中的最大和最小的元素；
2. 从当前层的剩余的元素中按照随机算法选出一定数量n的元素，n+2小于当前层元素个数；
3. 将所有选出的元素组成有序链表，作为当前层的上一层链表；
4. 给新增的链表中的所有元素添加一个指针域，该指针指向下一层中元素的值与自己相等的元素。
重复步骤2，直到当前层的只剩下最大和最小的两个元素为止。

C语言中常使用结构体+可变长数组的结构作为节点，如：

typedef struct NodeStructure {
		int key;
		int value;
		struct NodeStructure* forward[1]; // struct hack,可变长数组
}Node;

这样做的的好处在于所有层的值相同的节点共享一个节点，通过可变长数组实现不同层的定位。

注：C++由于虚表指针的位置存放在对象的最末端（一般是在对象起始位置，由编译器决定），因此struct hack不适应与C++对象。

插入
1. 新建一个数组update，长度为当前跳表的最大层数值。
2. 从高层往下遍历，查找新节点在每一层的插入位置，即新节点在该层的上一个节点，将该节点放入update。
3. 生成一个随机数k用于表示新节点即将插入的层数。如果该值大于当前层数n，则需要更新链跳表。
  1. 在更高层新建k-n层，并将新建层的头指针指向跳表头指针。
  2. 更新跳表的层数为k。
4. 基于k值，逐层插入新节点，与普通链表插入操作一样。
删除

删除操作与插入操作的前两步一样，使用update数组记录删除的位置，然后逐层删除目标节点。

不同之处在于，如果目标节点是当前层的最大值，则需要更新跳表的层数。
查询
1. 从高层往下查找，逐层遍历。
2. 在该层找到值小于或等于目标节点的节点：
  1. 如果当前节点的值等于目标节点，则查找完成。
  2. 否则，从当前节点进入下一层，继续向后查找。
3. 否则进入下一层遍历。

跳表是按层构造的，底层是一个有序链表，而更高层是按某个固定的概率p从下一层选取元素，换言之下一层的元素个数是上一层的1/p倍。

时间复杂度

跳表的时间复杂度取决于跳表的层数，跳表的层数为log(1/p)^n。且p是常数，所以跳表的查询、插入和删除操作的平均时间复杂度为O(logn)，最坏情况是退化为链表的复杂度O(n)。
空间复杂度

假设底层链表的元素个数为n，那么第i级索引的个数为n/(p^i)。跳表所有节点的总和是：∑ = n + n/(p^1) + n/(p^2) + n/(p^3) + … + 1，又因为p是常数，所以跳表的平均空间复杂度为O(n)。

最坏情况是每一层都与底层链表的元素个数相同，此时空间复杂度为O(nlogn)。