一种高效的链表数据结构，支持 O(log n) 的查找、插入和删除
跳表在底层链表之上建立了多层索引。顶层节点可以快速跳过大量元素，就像在图书馆的分类目录中快速定位。
新节点随机决定提升到哪一层（抛硬币决定）。平均每 2 个节点有 1 个在 L1，每 4 个有 1 个在 L2，以此类推。
从顶层开始，向右找到比目标大的最近节点，然后下降到下一层。重复直到最底层，平均只需 log n 步。
不像红黑树需要旋转维护平衡，跳表通过概率分布自然保持平衡。插入和删除只需局部修改指针。
| 操作 | 数组 | 普通链表 | 跳表 | 红黑树 |
|---|---|---|---|---|
| 查找 | O(log n) | O(n) | O(log n) | O(log n) |
| 插入 | O(n) | O(1)* | O(log n) | O(log n) |
| 删除 | O(n) | O(1)* | O(log n) | O(log n) |
| 范围查询 | O(log n + k) | O(n) | O(log n + k) | O(log n + k) |
| 实现难度 | 简单 | 非常简单 | 简单 | 复杂 |
* 需先 O(n) 找到位置后才能插入/删除