原文：https://lotabout.me/2018/skip-list/

跳表──没听过但很犀利的数据结构

跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

层的节点个数为：

于是代入 nL(n)=1/p">nL(n)=1/p

。

最高的层数

上面推导到每层的节点数目，直观上看，如果某一层的节点数目小于等于 1，则可以认为它是最高层了，代入 npl−1=1">npl?1=1

。

实际上这个问题并没有直接的解析解，我们能知道的是，当 n">n

，详情可以参见我的另一篇博客最高楼层问题。

搜索的时间复杂度

为了计算搜索的时间复杂度，我们可以将查找的过程倒过来，从搜索最后的节点开始，一直向左或向上，直到最顶层。如下图，在路径上的每一点，都可能有两种情况：

O(n)">O(n)">O(n/2)">⌈n2k⌉+k">k">⌈log2⁡n⌉">log⁡n">O(log⁡n)">l+1">nl+1=nlp">l">L(n)=log1/p⁡n">Lmax=log1/p⁡n+1=L(n)+1=O(log⁡n)">O(log⁡n)">

1. 节点有上一层的节点，向上。这种情况出现的概率是 p。
2. 节点没有上一层的节点，向左。出现的概率是 1-p。

于是，设 C(k) 为反向搜索爬到第 k 层的平均路径长度，则有：

C(0) = 0
C(k) = p * (情况1) + (1-p) * (情况2)

将两种情况也用 C 代入，有：

C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
C(k) = C(k–1) + 1/p
C(k) = k/p

上式表明，搜索时，平均在每层上需要搜索的路径长度为 1/p">1/p

，从平均的角度上和我们第一小节构造的“静态”结构相同（p 取 1/2）。

又注意到，上小节我们知道跳表的最大层数为 O(log⁡n)">O(logn)

。

P.S. 这里我们用到的是最大层数，原论文证明时用到的是 L(n)">L(n)

层到最高层的平均节点个数。这里为了理解方便不再详细证明。

小结

1. 各种搜索结构提高效率的方式都是通过空间换时间得到的。
2. 跳表最终形成的结构和搜索树很相似。
3. 跳表通过随机的方式来决定新插入节点来决定索引的层数。
4. 跳表搜索的时间复杂度是 O(log⁡n)">O(logn)

4. ，插入/删除也是。

想到快排(quick sort)与其它排序算法（如归并排序/堆排序）虽然时间复杂度是一样的，但复杂度的常数项较小；跳表的原论文也说跳表能提供一个常数项的速度提升，因此想着常数项小是不是随机算法的一个特点？这也它们大放异彩的重要因素吧。