跳表

跳表在很多数据结构的书中都不会提到，但是由于Redis的zset底层有时是基于跳表实现的，因此跳表这个数据结构在面试时成为一个有概率被问起的热点问题。

In computer science, a skip list (or skiplist) is a probabilistic data structure that allows $O(logn)$ average complexity for search as well as $O(logn)$ average complexity for insertion within an ordered sequence of n elements.

从维基百科中的定义我们可以了解到，跳表最重要的特性是对于一个有序列表，可以在对数复杂度内搜索一个数，并且可以在对数时间复杂度内插入一个数。下面列举了跳表复杂度相关的内容，

-	平均	最差情况下
空间复杂度	$O(n)$	$O(nlogn)$
搜索一个元素	$O(logn)$	$O(n)$
插入一个元素	$O(logn)$	$O(n)$
删除一个元素	$O(logn)$	$O(n)$

跳表的结构

跳表是一个多层的结构，第一层就是普通的有序链表，包含了序列中所有元素，如下图所示。仅有一层结构的跳表与普通的数据结构链表并无而致，为了提高跳表的性能，第一层之上添加了若干层，这些层有个fashion的名字——express lane(快车道)。

对于如何从第$i$层逐层向上构建，维基百科给了这样一种说法：

给定一个固定的概率$p$(通常是$1/2$或者$1/4$)，第$i$层中的节点以概率$p$的可能性出现在第$i+1$层。在平均情况下，每个节点会出现在$1/(1-p)$个链表中，且顶层的元素会出现在每一层链表中。整个跳表平均包含$log_{1/p}n$个链表。逐层构建好的跳表如下图所示:

跳表的操作

1. 查询：

1. 从顶层开始，每次找到最后一个小于key的节点n（如果等于，直接返回已找到；如果没找到这样的节点，则直接返回不存在），然后向下一层到第i层
2. 从当前层继续重复步骤1，如果未返回找到或不存在，则从n'所在层i再往下一层到i-1层；
3. 重复步骤2操作

2. 插入:

插入也可以沿用查询操作时的逻辑判断，每次都从当前层找到最后一个小于key的节点n，插入的位置就是第1层节点n所在位置。

3. 删除:

同样的，我们每次都找到最后一个小于key的节点，直到第1层。将第1层中最后一个小于key的节点的后续第一个节点删除即可完成该操作。

参考资料:

[1]: https://en.wikipedia.org/wiki/Skip_list

[2]: https://oi-wiki.org/ds/skiplist/