原创声明

本文修改自：https://www.iteye.com/blog/kenby-1187303。

有序链表的搜索

设有如下有序链表：

从该有序链表中搜索元素 <23, 43, 59>，需要比较的次数分别为 <2, 4, 6>，总共比较的次数是 2 + 4 + 6 = 12 次。类似二叉搜索树，我们把一些节点提取出来，作为索引，得到如下结构：

这里我们把 <14, 34, 50, 72> 提取出来作为一级索引，这样搜索时可以减少比较次数。我们还以从一级索引中提取出一些元素作为二级索引，变成如下结构：

跳表

下面是一个跳表的实例，其中 -1 表示 INT_MIN，即元素的最小值；1 表示 INT_MAX，即元素的最大值：

跳表具有如下性质：

• 包含多层
• 每层是一个有序链表
• 最底层的链表包含所有数据元素
• 如果一个元素出现在第 i 层的链表中，那么它一定出现在第 i 层以下的所有链表中
• 每个节点包含两个指针：
  • 一个指向同一链表中的下一个节点
  • 一个指向下一层的节点

跳表的插入

采用丢硬币的方式确定元素要占据的层数 K，然后在第 1 到 K 之间的各层都插入元素。

例子：插入 119，K = 2

如果 K 大于当前层数，则需要添加新层。

例子：插入 119，K = 4

跳表的删除

在各层中找到包含待删除元素的节点，然后使用标准的 delete from list 方法删除相应节点。

例子：删除 71

跳表的搜索

例子：查找元素 117

(1) 比较 21， 比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85， 比 85 大，从后面找

(5) 比较 117， 等于 117， 找到了节点

具体搜索算法如下：

node = top;
while (node 非空) {
    while (node 的下一个节点非空 并且 node 的下一个节点的关键字小于目标关键字)
        node = node 的下一个节点；
    if (node 的下一个节点非空 并且 node 的下一个节点的关键字等于目标关键字) {
        node = node 的下一个节点;
        while (node 对应的下层节点非空)
            node = node 对应的下层节点;
        return node;
    }

    // 去下层寻找
    node = node 对应的下层节点;
}

Python 实现