数据结构中的跳跃表

什么是跳跃表？

跳跃表是一种概率数据结构。跳跃表用于存储带有链表的排序元素或数据列表。它允许高效地处理元素或数据。它在单个步骤中跳过整个列表的多个元素，这就是为什么它被称为跳跃表。

跳跃表是链表的扩展版本。它允许用户非常快速地搜索、删除和插入元素。它由一个包含一组元素的基础列表组成，该列表维护后续元素的链接层次结构。

跳跃表结构

它分为两层构建：最底层和顶层。

跳跃表的最底层是一个普通的排序链表，而跳跃表的顶层就像一条“快速通道”，其中的元素被跳过。

跳跃表复杂度表

跳跃表的工作原理

让我们举一个例子来理解跳跃表的工作原理。在这个例子中，我们有 14 个节点，这些节点分为两层，如图所示。

下层是连接所有节点的普通线，上层是只连接主节点的快速线，如图所示。

假设您想在此示例中查找 47。您将从快速线的第一节点开始搜索，并在快速线上继续运行，直到找到等于 47 或大于 47 的节点。

您可以在示例中看到 47 不存在于快速线中，因此您搜索小于 47 的节点，即 40。现在，您借助 40 转到普通线，并搜索 47，如图所示。

注意：一旦您在“快速线”上找到这样的节点，您将使用指针从该节点转到“普通通道”，然后在普通线中搜索该节点。

跳跃表基本操作

跳跃表中有以下几种操作。

• 插入操作： 它用于在特定情况下将新节点添加到特定位置。
• 删除操作： 它用于在特定情况下删除节点。
• 搜索操作： 搜索操作用于在跳跃表中搜索特定节点。

插入操作算法

删除操作算法

搜索操作算法

示例 1： 创建一个跳跃表，我们想在空跳跃表中插入以下键。

1. 6，级别 1。
2. 29，级别 1。
3. 22，级别 4。
4. 9，级别 3。
5. 17，级别 1。
6. 4，级别 2。

答

步骤 1： 插入 6，级别 1

步骤 2： 插入 29，级别 1

步骤 3： 插入 22，级别 4

步骤 4： 插入 9，级别 3

步骤 5： 插入 17，级别 1

步骤 6： 插入 4，级别 2

示例 2： 考虑这个例子，我们想搜索键 17。

答

跳跃表的优点

1. 如果您想在跳跃表中插入新节点，那么它将非常快地插入节点，因为跳跃表中没有旋转。
2. 与哈希表和二叉搜索树相比，跳跃表实现起来更简单。
3. 在列表中查找节点非常简单，因为它以排序形式存储节点。
4. 跳跃表算法可以很容易地修改成更具体的结构，例如可索引跳跃表、树或优先级队列。
5. 跳跃表是一个健壮可靠的列表。

跳跃表的缺点

1. 它比平衡树需要更多的内存。
2. 不允许反向搜索。
3. 跳跃表搜索节点比链表慢得多。

跳跃表的应用

1. 它用于分布式应用程序中，表示分布式应用程序中的指针和系统。
2. 它用于实现具有低锁争用的动态弹性并发队列。
3. 它也与 QMap 模板类一起使用。
4. 跳跃表的索引用于运行中位数问题。
5. 跳跃表用于 Lucene 搜索中的增量编码发布。