有了红黑树，为啥还要跳表？
书接前文。
前文书《红黑树是怎么来的》我们讲了通过红黑树（本质上是 2-3 树或者 2-3-4 树思想）来维护二叉搜索树的平衡性。从红黑树的实现来看，虽然相对于 2-3 树来说是简化了不少，但仍然是相当复杂的。
有没有更加简单的实现方案呢？
源于二分思想
在前文《二叉搜索树的本质》中我们通过将有序数组的二分查找链表化，最终得到二叉搜索树。
这次，我们还是从有序数组的二分查找开始，看看能否发明什么新的数据结构。
和以前不同的是，这次我们先将有序数组链表化：
如图。现在我们考虑如何在该链表中查找元素 40。
最简单的做法是从表头开始往后遍历，时间复杂度 O(n)——显然不是我们想要的。
我们的初步想法是：能否在这个链表上执行二分搜索？
对于数组来说，我们可以通过地址偏移立即定位到中间元素（15），然后发现 40 比 15 大，继续对 15 后面的元素执行二分查找即可。
链表的困境在于，它没法通过地址偏移来快速定位元素。
不过我们并不死心——有没有什么奇技淫巧来模拟链表上的二分查找？
既然对于链表，只能通过指针来遍历元素，那我们能否通过给节点 1、15、60（头尾以及二分查找涉及到的中间元素）之间建立额外的指针来实现快速跳转呢？
如图：
我们建立了一个额外的链表（1→15→60），且该链表的每个节点都有一个额外指针指向下一层的同名节点。
有什么用呢？
再来看看如何查找元素 40。
我们可以先查上面（第二层）那个链表，只需两步就走到元素 15，发现 40 介于 15 和 60（15 的下一个元素）之间，于是我们通过 15 的“下降”指针来到第一层链表同名节点 15，然后在第一层链表中继续往后查找。
如图：
和直接在原始链表上遍历不同，通过添加一层“索引”链表，我们能和二分查找一样“直达”中间元素，搜索效率一下子提升了一倍。
那么，这个查询能否再优化一下呢？
上图中，15 以后的搜索仍然是线性的。我们同样可以对 1-15、15-60 之间的两段子链表再次建立“索引链表”：
乍看有点小复杂，实际上它仍然是对二分查找的模拟。
我们从上层往下层看。
第三层相当于执行第一次二分，标的元素是 15，然后根据实际情况到 1-15 或者 15-60 区间去查找。
第二层则是在第三层（第一次二分查找）的基础上做的第二次二分，得到更细粒度的查找区间。
所以说，如果我们从最上层索引链表往最下层方向逐层查找，就相当于模拟有序数组一次次的二分查找。
妙哉！
我们看看建立两层索引后元素 40 的查找路径：
和一层相比，查找路径要短很多。
和普通链表相比，这种链表通过索引“跳过”了一些节点，以提升搜索效率，因而我们给它起个“望文生义”的名字就叫跳表（skiplist）。
由于跳表本质上是对二分法的模拟，所以其搜索时间复杂度同二分搜索一样是 O(logn)。
数据结构
跳表的节点（最底层除外）除了要指向后继节点（如果是双向链表还要指向前驱节点），还需要指向下层同名节点，所以节点结构初步定义如下：
class Node {
key: number
val: unknown
// 后继节点
next: Node | null
// 下层节点（比普通链表多出来的指针）
down: Node | null
public constructor(key: number, val: unknown) {
// ......
}
}
上图中节点 15 表示如下：
// 第三层的 node15
const node15_l3: Node = {
key: 15,
val: 15,
next: node60_l3,
down: node15_l2,
}
// 第二层的 node15
const node15_l2: Node = {
key: 15,
val: 15,
next: node30_l2,
down: node15_l1,
}
// 第一层的 node15
const node15_l1: Node = {
key: 15,
val: 15,
next: node20_l1,
down: null,
}
我们分析一下上面的数据结构定义有没有什么问题。
首先说明一点，通过建立索引链表来提升搜索速度属于典型的用空间换时间。
不过，我们为同一个元素（如上例中的 15）在每一层都建立了一个独立的对象——这是不是过于铺张浪费了？
我们分析一下上面三个 object 的特点，看看有没有什么优化空间：
- 三个节点的 key、val 都是一样的；
- 最大的不同在于 next 指针，三个节点的 next 都不一样；
- 由图可知，上层节点总是逐层下潜的（即第 n 层节点的 down 指针总是指向第 n - 1 层的同名节点）；
所以我们可以尝试将同一元素的各层节点合而为一：
class Node {
public key: number
public val: unknown
// 该节点各层的后继节点指针数组
public nexts: (Node | null)[]
public constructor(key: number, val: unknown) {
// ......
}
}
如上，我们将 next 和 down 两个指针合入到 nexts 指针数组中，nexts[i] 表示该节点在第 i + 1 层的后继节点。
改造后图示如下：
如上图，我们做了四方面的改造：
- 各层的同名节点（同 key）合并成一个节点；
- 引入 nexts 指针数组，node.nexts[i] 表示节点 node 在第 i + 1 层的后继节点；
- 为编码上的方便，引入哨兵节点 head（不表示任何实际节点）；
- 不再对尾节点（图中的 60）建立索引（没有必要，编程中用 null 值判断即可）；
最后我们定义出完整的数据结构：
class SkipList {
// 表头指针。为方便处理，表头不表示实际节点， 作为哨兵存在
protected head: Node
// 跳表中元素个数
protected length: number
// 跳表层数
protected level: number
public constructor() {
// 创建表头
this.head = new Node(-Infinity, undefined)
this.length = 0
this.level = 0
}
}
查找元素
我们看看如何查找节点 40。
任何查找都从表头 head 且从最上层开始，到第一层为止：
- 取 head.nexts[2]，是 15，小于 40，则取 node15 继续比较；
- 取 node15.nexts[2]，是 null，说明不能再往后找了，则下降到第二层（nexts 下标 1）；
- 取 node15.nexts[1]，是 30，小于 40，则取 node30 继续比较；
- 取 node30.nexts[1]，是 null，说明不能再往后找了，则下降到第一层（nexts 下标 0）；
- 取 node30.nexts[0]，是 40，找到，返回并结束；
如图：
代码如下：
class SkipList {
// ......
/**
* 根据 key 查找 value 并返回，如果没找到则返回 undefined
* @param key
*/
public search(key: number): unknown {
if (!this.length) {
return
}
// 从 head 开始找
let node = this.head
// 从最高层开始往下搜索，直到搜到第一层
for (let i = this.level - 1; i >= 0; i--) {
// 如果当前节点该层存在后继节点，且该后继节点的 key 小于等于目标 key，则跳到该后继节点
while (node.nexts[i] && node.nexts[i].key <= key) {
node = node.nexts[i]
}
// 从 node 进入到下一层继续查找
}
return node.key === key ? node.val : undefined
}
}
超简单有没有！
索引层数
在讲插入之前，我们先思考一个问题：链表中的某个元素应该有多少层（或者说需要给它建多少层索引）？
前面我们通过二分法推导出多层索引的概念。但如果在实际操作中，每次插入一个元素后都用二分法思想去确定元素的索引层数，可能一次插入会导致大范围的索引重建（比如原本通过二分法拿到标的节点是 a，插入新元素后再次二分拿到的标的很可能不再是 a）。
我们也可以采用类似 B 树的裂变思想，比如我们规定第 n 层两个节点之间所囊括的 n - 1 层元素数量不可超过 x，一旦超过就触发裂变以生成新的索引（裂变可能是级联的）。不过其实现起来也比较复杂。
跳表的设计采用了一种简单粗暴但很有效的方法：概率法。
思想是这样的：我们规定第 n 层的元素数量是其下一层（n - 1）数量的 1/N。换句话说，一个元素有 1/N 的概率会向上建一层索引。
以 N = 4 为例。
假设我们想插入元素 22——该元素需要建立几层索引呢？
有 3/4 的概率不建立任何索引（也就是只有最底下一层）。
有 1/4 的概率建立 1 层索引。
有 1/4 * 1/4 即 1/16 的概率建 2 层索引。
有 1/4 * 1/4 * 1/4 即 1/64 的概率建 3 层索引。
依此类推。
如此得到的数据结构本质上是一棵 N 叉树（这里是 4 叉树）。
我们通过如下代码计算一个新节点的层数信息：
class SkipList {
// 最大层数限制
protected static readonly MAX_LEVEL = 32
// 上层元素数是下层数量的 1/N（相当于 N 叉树）
protected static readonly N = 4
// ......
/**
* 随机生成 level 层数
* 从最底层开始，每增加一层的概率为 1/N
*/
protected randomLevel(): number {
let level = 1
while (Math.round(Math.random()*10000000) % SkipList.N === 0) {
level++
}
return Math.min(level, SkipList.MAX_LEVEL)
}
}
这里我们通过将生成的随机数对 N 取模和 0 比较来模拟 1/N 的概率（比如 N = 4，则取模后为 0-3）。
插入元素
我们看如何插入元素 22。
首先要确定 22 在原始链表（第一层链表）中的位置，该过程实际就是搜索过程，时间复杂度 O(logn)。
搜索过程如图：
我们找到应该在 20 和 25 两个节点之间插入 22。
假如我们通过 randomLevel() 得到层数是 5，插入后整个跳表长这样：
观察上图发现：
- 每层都有 next 指针指向该新节点，具体来说就是搜索路径上各层最右搜索节点（15、15、20）的 next 指针指向新节点；
- 新层（最高两层）的前驱节点都是 head；
- 新节点的各层 next 指针指向该层前驱节点的 next 原值；
经上面分析发现，整个插入过程中，关键是找出每层的前驱节点。代码如下：
class SkipList {
/**
* 搜索关键字 key，返回其搜索路径上经过的每层的前驱节点数组
* 即每层返回其左边相邻节点
* @param key - 关键字
* @returns 关键字 key 在每层的前驱节点数组
*/
private searchPrevNodes(key: number): Node[] {
// 记录每层走到的最右边的位置（也就是目标节点的前驱节点）
const prevNodes: Node[] = []
// 从 head 开始
let node = this.head
// 从最上层开始往下找
for (let i = this.level - 1; i >= 0; i--) {
// 如果当前节点该层存在后继节点，且该后继节点的 key 小于 key，则跳到该后继节点
while (node.nexts[i] && node.nexts[i].key < key) {
node = node.nexts[i]
}
// 下沉之前记录该节点作为本层访问到的最右节点
prevNodes[i] = node
}
// 如果一个都没有（列表为空，this.level = 0 时），将 head 加入进去
if (!prevNodes.length) {
prevNodes[0] = this.head
}
return prevNodes
}
}
元素插入逻辑代码如下：
class SkipList {
// ......
/**
* 将 { key, val } 插入到跳表中
*/
public insert(key: number, val: unknown) {
// 获取搜索路径上的各层前驱节点
const prevNodes = this.searchPrevNodes(key)
// 创建新节点
const newNode: Node = { key, val, prev: null, nexts: [] }
// 计算新节点的索引层数
const level = this.randomLevel()
// 逐层处理 next 指针
for (let i = 0; i < level; i++) {
// prevNodes 里面仅有原先 this.level 层的最右 node，而新 level 可能高于原 level，
// 该情况下，超出的层在 prevNodes 里面没有对应节点，则直接取 head
const leftNode = prevNodes[i] ?? this.head
// 变更 next 指针
newNode.nexts[i] = leftNode.nexts[i]
leftNode.nexts[i] = newNode
}
if (level > this.level) {
this.level = level
}
this.length++
}
}
插入过程的平均时间复杂度是 O(logn)。
删除元素
考虑删除节点 22，删除后整个跳表结构如下：
跳表元素的删除本质就是插入的逆操作：将该节点从各层抹除，即将该节点各层的前驱节点的 next 指针指向该节点在该层的后继节点。
插入过程中可能产生新的层（head 层数随之增长），而删除则可能造成层数减少（head 层数收缩）。
通过观察图示不难发现，删除后和插入前的结构竟然是一模一样的，如此的稳定性真让人叹为惊奇。
不同于其他平衡树，跳表的插入和删除不但完全互逆，而且也没有复杂的递归重建过程——这正是跳表这种概率型数据结构的简单性之精华所在。
删除代码如下：
class SkipList {
// ......
public delete(key: number) {
// 获取搜索路径上的各层前驱节点
const prevNodes = this.searchPrevNodes(key)
// 待删除的节点就是第一层前驱节点的该层 next 指针所指向的节点
const current = prevNodes[0].nexts[0]
if (!current || current.key !== key) {
return
}
// 从下往上，处理各层的 next 指针
// 需要处理的层：待删节点的索引层数
for (let i = 0; i < current.nexts.length; i++) {
prevNodes[i].nexts[i] = current.nexts[i]
current.nexts[i] = null
// 如果该层的前驱节点是 head，且调整后其 next 指向 null/undefined，说明该层不再有有效节点，需要将层数减 1
if (!this.head.nexts[i]) {
this.level--
}
}
this.length--
}
}
简单性的源头
对比红黑树的插入和删除实现，你会惊于跳表的实现是如此简单。为何？
我们假设不使用概率来决定新节点的索引层数，就很可能需要采用类似 B 树的方案，通过限制两索引节点之间所辖节点数来决定索引的分裂与合并。比如规定任何两索引节点之间所辖节点数必须在 N/2 到 N 之间，小于 N/2 则谋求合并，超过 N 则分裂。如此必然会带来复杂的级联分裂与合并逻辑。
相反，跳表采用了简单粗暴但同样有效的概率法，在插入元素的时候，通过概率计算得出索引层数，而更新索引（插入和删除）仅影响该节点在各层的前驱节点，影响非常小，更新过程异常简单。
所以说，这种数据结构的概率性带来了其简单性。
总结
- 我们通过有序数组的二分查找思想推导出链式数据结构的二分法：多级索引；
- 通过概率决定每个元素的索引层数，在理论正确性的前提下保证了实现的简单性；
- 插入和删除操作的关键是找出目标节点在每层的前驱节点；
- 插入和删除操作是完全互逆的，表明跳表具备很好的动态稳定性；
- 跳表和红黑树的各项操作具备同级别的时间复杂度，但比红黑树实现起来更加简单，范围查询也更加直观高效（直接定位到起始节点，然后直接在第一层顺序遍历即可），所以现在很多项目都采用了跳表这种数据结构（如 Redis、Lucene、LevelDB 等）；
另外，分级索引是人类信息检索领域的一个重要思想，图书检索、书本目录、文件系统、域名（DNS 查询）、ip 地址、操作系统页表等等的设计都体现了该思想。
本文完整代码参见 github: https://github.com/linzier/algo-ts。
为讲解的简单性，本文使用的是单向链表，github 中实现的是双向链表。