题目与范围
实现一个整数有序集合，支持 search、insert 和 delete。目标是期望 O(log n)，并避免平衡树旋转。先说明重复键规则；本文选择集合，因此插入已有键时不改变结构。
公开面经和实现讨论包含跳表题目，例如 Google 面试题和 LeetCode 面试贴。考察重点是维护多层前向指针并证明不变量，不是记住某个库类。
面试官考察什么
- 是否保持第 0 层包含完整有序链，所有高层都是它的子序列。
- 插入和删除是否更新每一层前驱而不破坏底层链接。
- 是否区分期望
O(log n)和随机性不利时的O(n)，并测试随机层高边界。
Redis 的有序集合编码使用跳表，MIT 算法讲义给出了概率分析。它们分别是实现和理论证据，不代表所有工作负载都应以跳表替代树。
作答前澄清
- 集合还是多重集合？ 集合拒绝重复键；多重集合需要计数或唯一节点标识。
- 是否需要排名或范围查询？ 排名需要跨度元数据；基础题只要求成员判断。
- 是否需要确定性重放？ 测试使用带种子的随机源，生产使用无偏随机生成器。
- 内存上限是多少？ 节点拥有可变数量的前向指针，层数上限和晋升概率都会影响内存。
30 秒回答
“我用一个每层都有前向指针的哨兵，以及按键排序的第 0 层链。查找从最高层开始，只有下一个键更小时才前进，并记录每层最后一个前驱。插入生成随机层高，把新节点接到这些前驱之后；已有键直接返回。删除使用同一组前驱，在节点出现的每层解除链接，再在顶层为空时降低活动层数。几何层高带来期望 O(log n) 的查找、插入和删除，期望空间为 O(n)；随机序列极端时仍可能是 O(n)。”
分步深答
第一步：定义不变量。
第 0 层包含所有键且严格递增。第 i + 1 层是第 i 层的子序列，每个节点的前向指针按键排序。哨兵没有用户键，但有 MAX_LEVEL 个指针。活动层是最高的非空层。
第二步：查找并收集前驱。
从哨兵的最高活动层开始。只要下一个节点存在且键小于目标就向前走；下降一层后继续。把每层最后访问的节点存到 update[i]。到达第 0 层后，update[0].next[0] 要么是目标，要么是插入位置。
第三步：用随机层高插入。
用晋升概率 p = 1/2 的几何过程生成层高，并限制在 MAX_LEVEL。若第 0 层候选键相同，返回 false。对新节点覆盖的每一层，先保存前驱的下一个节点，再让前驱指向新节点。若层高超过当前活动层，就扩展活动层。
第四步：在所有出现的层删除目标。
前驱数组给出每层目标节点的前驱。只有当 update[i].next[i] 正是目标时才解除该层链接；更高层可能没有目标。删除后，只要哨兵顶层指针为空，就降低活动层。
第五步：分析复杂度和内存。
当晋升概率在 0 和 1 之间时，期望层高为常数，期望搜索路径为对数级。查找、插入和删除期望 O(log n)，随机不利时最坏 O(n)。期望指针数与 n/(1-p) 同阶，因此 p = 1/2 用约两倍指针换取较短路径。
第六步：测试结构、随机性和边界。
测试使用带种子的随机源。覆盖空集合、首尾键、重复插入、删除唯一节点、跨多层删除、负数和反复插删。每次操作后把第 0 层与参考 Set 对照，并验证每个高层有序且节点都出现在第 0 层。运行多组种子捕获层高和指针损坏。
高质量示范回答
“我把它建模为带哨兵的集合，第 0 层是有序链，所有高层都是第 0 层的子序列。查找从最高活动层下降，同时记录每层前驱。插入拒绝重复键，生成几何随机层高并在前驱之后插入；删除找到同一前驱数组，在节点出现的每层解除链接，并清理空的顶层。
操作期望 O(log n)、期望空间 O(n)，但随机层高不利时最坏是 O(n)。我会在测试中使用带种子的随机源，每次操作都和参考集合比较，并检查排序及子序列不变量。”
常见错误
- 只更新第 0 层 → 高层查找会跳过或保留该键 → 在节点出现的每层插入或解除链接。
- 把随机层高当成保证 → 极端序列可能形成线性路径 → 同时说明期望和最坏边界。
- 无意中允许重复节点 → 查找和删除语义不明确 → 先选择集合或多重集合。
- 删除后不清理空顶层 → 搜索检查过时层，状态逐渐漂移 → 删除后降低活动层。
- 只测试最终成员 → 损坏的高层指针可能隐藏 → 每次操作都检查排序和子序列不变量。
追问与回答
追问 1：如何支持重复键？
先定合同。多重集合可在每个键节点存计数，让重复插入和删除只修改计数；也可以把唯一序号并入比较键。内存允许时计数更简单；需要删除某个具体出现时，唯一标识更合适。
追问 2：如何加入排名查询？
在每个前向指针旁保存跨度。查找向右移动时累加跨度，插入和删除在每层更新受影响跨度。简单集合实现没有足够元数据，不能直接以对数时间回答排名。
追问 3：什么时候选择平衡树？
当最坏边界、确定性迭代形态或丰富有序操作比实现简洁更重要时，选择平衡树。跳表适合接受期望性能、希望实现指针型有序索引或需要容易扩展并发变体的场景。应测量内存和工作负载，不要声称一种结构总是更快。