什么是跳跃表，它如何实现 O(log n) 的搜索？

Question

Accepted Answer

**跳跃表**（skip list）是一个有序链表，通过多个**"快速通道"**层级进行增强。高层级节点会跳过许多节点，因此搜索会向下并向右移动，实现 **O(log n)** 期望时间复杂度——这是平衡树的一种概率性的、更简单的替代方案。 ## 结构 ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` 每个节点以概率 `p`（通常为 0.5）被提升到更高的层级，因此平均而言每一层的节点数是其下方层级的一半。 ## 搜索 ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## 复杂度 | 操作 | 期望 | 空间 | |---|---|---| | 搜索 | O(log n) | O(n) | | 插入 / 删除 | O(log n) | — | ## 与平衡树的权衡 - **优点：** 比红黑树/AVL 树简单得多；无需旋转；易于并发版本（在 Redis 有序集、Java `ConcurrentSkipListMap` 中使用）。 - **缺点：** 概率性保证（非最坏情况）；每个节点需要额外指针。 ## 为什么这很重要跳跃表用极少的代码实现了树形的 O(log n) 有序操作，并且支持简便的无锁并发，这正是为什么 Redis 等实际系统选择采用它的原因。这是使用**随机化**来替代复杂的确定性平衡逻辑的绝佳范例。