13 跳表
跳表: 链表上的“二分查找”
1. 特性
跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。实现上跳表使用空间换时间的思想，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。
1.1 跳表的结构
跳表就是在有序链表的基础上添加了多层"索引"。通过每隔几个节点提取一个节点形成上层索引，每层索引的节点个数成等比数列分布，从顶向下的每次查询都会将查询区间“折半”，从而达到 O(logN) 的时间复杂度。每次查询对查询区间的缩减取决于索引构建策略，通过改变索引构建策略，有效平衡执行效率和内存消耗。待会我们会看到更加具体的分析过程。
跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。Redis 中的有序集合（Sorted Set）就是在跳表的基础上实现的。
1.2 跳表的查找
假设我们每隔两个节点构建一层索引，最上层有两个节点，总共有 N 个节点。则第 h 层的节点个数为 N/2^h，包含最底层的链表在内总共有 logN 层。如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。对于每隔两个节点构建的索引 m=3。
原因是，假设我们要查找的数据是 x，在第 k 级索引中，我们遍历到 y 结点之后，发现 x 大于 y，小于后面的结点 z，所以我们通过 y 的 down 指针，从第 k 级索引下降到第 k-1 级索引。在第 k-1 级索引中，y 和 z 之间只有 3 个结点（包含 y 和 z），所以，我们在 K-1 级索引中最多只需要遍历 3 个结点，依次类推，每一级索引都最多只需要遍历 3 个结点。
所以在跳表中查询任意数据的时间复杂度就是 O(logn)。而整个跳表需要额外添加的节点数为n/2+n/4+n/8…+8+4+2=n-2，所以空间复杂度为 O(n)。
如果我们每三个结点或五个结点，抽一个结点到上级索引。总的索引结点大约就是 n/3+n/9+n/27+…+9+3+1=n/2，而查询时间复杂度的系数就会从 3 变成 4。因此通过改变索引构建策略，有效平衡执行效率和内存消耗。
1.3 跳表的插入
跳表的插入有两个要点:
- 要保证原始链表中数据的有序性
- 要维护索引与原始链表大小之间的平衡，避免复杂度退化
因此在插入前需要先找到插入位置，然后通过一个随机函数，来决定将这个结点插入到哪几级索引中。整个过程的时间复杂度= O(logn)(查找) + O(1)(链表的插入)
1.4 跳表的删除
删除的过程只是在查找的基础上多了链表的删除操作，对于双向链表而言删除的时间复杂度也是 O(logn)。需要注意的是删除的节点也可能出现在索引中，需要一并删除。
1.5 跳表与红黑树
跳表和红黑树都是非常高效的动态数据结构，在插入、删除、查找以及迭代输出有序序列上，时间复杂度都是 O(logn)。但是存在以下不同:
- 按照区间来查找数据，跳表比红黑树更加高效，跳表可以在 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历即可
- 相对于红黑树跳表更加简单灵活，通过改变索引构建策略，可以有效平衡执行效率和内存消耗
- 红黑树出现的更早，很多编程语言中的 Map 类型都是通过红黑树实现的。可以直接拿来用，但是跳表并没有一个现成的实现，想要使用必须自己实现。
2. 实现
跳表的实现有以下几个关键点:
- SkipNode 表示调表中的一个节点，每个SkipNone都包含一个
next=[SkipNone]:- len(next) 就是当前节点的层高
- next[i] 表示第 i 层的后继节点
- 通过随机法，来决定一个节点的层数
- 无论查找，插入，还是删除，我们都需要获取带查找节点的前驱节点
- 查找前驱节点，必须从最顶层查找到最底层，因为需要保留每一层的前驱节点
- Go 语言中，我们还需要为保存的值实现接口
下面是调表的 Python 与 Go 实现。
2.1 Python 实现
下面是 Python 的跳表实现。
|
|
2.2 Go 实现
|
|
参考: