跳表 SkipList

跳表的结构

跳表是一种有序的数据结构，它将元素按顺序排列，并通过多层索引来加速查找过程。每一层都是一个 有序链表，但并不是每个元素都会出现在每一层。高层的链表是低层链表的简化版，包含较少的元素。通过跳跃式查找，能够提高查找效率。

基本概念

• 底层链表（Level 0）：存储所有的元素，保证有序。

• 上层链表（Level 1, Level 2, ...）：每一层的链表包含的元素较少，通常是随机选择的。跳表通过这些高层链表快速跳过不必要的元素。

示例

假设我们有一个有序的整数集合：[1, 3, 5, 7, 9, 11, 13, 15, 17]。我们将构建一个跳表。

跳表的构建过程

1. 底层链表 (Level 0)： 这是跳表的基本链表，包含所有的元素，按顺序排列：

[1] → [3] → [5] → [7] → [9] → [11] → [13] → [15] → [17]

2. 第二层链表 (Level 1)： 在 Level 1 上，我们随机选择一些元素来构建链表。例如，我们可以选择每隔一个元素取一个：

[1] → [5] → [9] → [13] → [17]

3. 第三层链表 (Level 2)： 再次随机选择一些元素。我们可以选择每隔两个元素取一个：

[1] → [9] → [17]

这个跳表有三层：底层包含所有元素，第二层每隔一个元素取一个，第三层每隔两个元素取一个。

最终的跳表结构：

Level 2:   [1] → [9] → [17]
Level 1:   [1] → [5] → [9] → [13] → [17]
Level 0:   [1] → [3] → [5] → [7] → [9] → [11] → [13] → [15] → [17]

查找元素

假设我们要查找数字 7，以下是跳表的查找过程：

1. 从最高层（Level 2）开始：

• 从 1 开始，检查 9。因为 9 大于 7，所以我们跳到下一层。

2. 移动到 Level 1：

• 从 1 开始，跳过 5（小于 7），继续跳到 9。

• 因为 9 大于 7，所以我们跳到 Level 0。

3. 移动到 Level 0：

• 在 Level 0 中，我们逐个查找，找到 7。

总结：通过这种多层链表的结构，查找过程中每次都可以跳过不必要的元素，从而加速查找。

插入元素

插入元素时，首先会决定插入的元素在各层链表中的位置。插入一个新的元素（例如 6）时，它会根据概率决定是否出现在 Level 1 或 Level 2 上。

跳表的优点

• 查找效率高：通过跳表的多层链表结构，可以在 O(log N) 时间内查找到目标元素。

• 插入和删除：插入和删除操作也能够在 O(log N) 的时间复杂度内完成。

时间复杂度：

• 查找：O(log N)

• 插入：O(log N)

• 删除：O(log N)

总结

跳表通过多层索引链表来加速查找过程，相比于单层链表，它能在查找、插入和删除时提供更高的效率。这种结构常常用于需要频繁查询和动态更新数据的场景，如 Redis 的 Sorted Set 中的有序数据存储。