ai-infra-interview-305

第 285 题：`skip list`的实现？`level`随机化策略？

题目

skip list的实现？level随机化策略？

完整讲解

一、Skip list 结构

跳表：多层有序链表，底层为完整有序链表，上层为「索引」、每层为下层的稀疏子集。从顶层头开始，向右走直到下一节点大于目标则下一层，直到底层找到或确定不存在。查找、插入、删除期望 O(log n)，实现简单，无需平衡（如红黑树）的复杂旋转。

二、Level 随机化

每个节点有一个 level（高度）；插入时用随机决定 level：常见策略为「以概率 p（如 1/2 或 1/4）加一层」，即 level 0 必选，level i+1 以 p 概率选。这样高层节点数约为下层的 1/p，形成类似「二分」的索引，期望层数 O(log n)。随机化避免刻意构造的退化，期望性能稳定。

三、实现要点

每节点含 forward 数组（各层后继）；头节点层高为最大层。查找：从最高层头开始，本层向右走到「下一个 > key」则下一层。插入：随机出 level，自顶向下找插入位置，在各层链入新节点。删除：找节点并在各层摘链。

面试要点

跳表：多层有序链表，上层为下层索引；查找从顶向右、大则下一层。
Level 随机化：插入时以概率 p 决定层高，形成 O(log n) 期望层数；避免退化。
每节点有各层 forward；头节点层高足够；插入/删除需维护各层指针。
期望 O(log n)；实现简单，Redis 等用跳表做有序结构。

记忆要点

多层链表，上层稀疏；查找从顶向右、大则下一层。
Level 随机：以 p 加层，期望 O(log n) 层。
实现：forward 数组、头节点、插入删除维护各层链。

返回模块

返回总览