数据结构与算法之美 | 学习笔记13 —— 跳表

对于链表不能采用二分查找方法，这时我们将链表稍加改造为跳表(Skip list)，就可支持类似“二分”的查找算法。

一、跳表

对原始链表建立多级索引结构，每两个结点提取一个结点到上面一层级，将抽出来的这个层级叫索引或索引层。图中down表示down指针，指向下一结点。查找时，先从顶层的索引层遍历，通过down指针下降层级，直到原始链表。

时间复杂度

如果链表里有n个结点，每两个结点抽出一个作为上一级索引的结点，那么第一级索引的结点个数为$\frac n2$2n​，第二层为$\frac n4$4n​，依次类推，第k级索引结点个数为$\frac {n}{2^k}$2kn​，假设索引共有h级，*有2个结点，则$\frac {n}{2^h}=2$2hn​=2，$h=log_2n-1$h=log2​n−1，加上原始链表这一层，整个跳表的高度即为$log_2n$log2​n。查询某个数据时，如果每一层都遍历m个结点，那么在跳表中查询一个数据的时间复杂度为$O(mlogn)$O(mlogn)。按照上图的索引结构，因为每两个结点提取一个索引结点，所以查询时每一级最多遍历3个结点，因此跳表中查询任意数据的时间复杂度为$O(logn)$O(logn)。

空间复杂度

每层索引的结点数为：

等比数列相加为n-2。（注意此处项数为$log_2\frac n2$log2​2n​），空间复杂度为$O(n)$O(n)。
如果每3个结点抽一个，那就是n/2。比两个结点的少了一半的存储空间。实际开发中，原始链表中存储的可能是很大的对象，而索引结点只要存储关键值和指针，并不需要存储对象，所以索引占用的额外空间可以就可以忽略了。

二、跳表的操作

跳表的动态插入和删除操作时间复杂度为$O(logn)$O(logn)。

1. 插入和删除

确定好要插入的位置后，插入操作的时间复杂度为$O(1)$O(1)。而确定位置的过程就是查找过程，因此整个插入操作的时间复杂度为$O(logn)$O(logn)。

删除的操作中，除了要删除原始链表中的结点，如果索引中出现，还要删除索引中的。当然，在删除操作时，对于单链表要获取前驱结点。

2. 跳表的动态更新

当频繁插入操作时，可能存在两个索引结点之间数据过多的情况，此时极端情况下可能会退化成单链表。

跳表通过随机函数来维护这种平衡性，往跳表中插入数据时，通过一个随机函数来决定结点插入到哪一级索引中，例如下图，就将插入数据同时建立第二层索引结点：

代码实现：王争的GitHub