跳表

层级模型 ​

第 0 层含全部有序键，并以多层链表公理库链表Linked list节点通过指针连接并支持局部插入删除的线性数据结构。保存前向指针。每个节点独立以概率 $p$ 晋升到下一层，故

$$\text{Pr}[H(x)\ge k]=p^k.$$

搜索从最高层头节点出发，能向右且不越过目标就前进，否则下降一层；插入记录每层前驱后按新节点随机高度接链，删除在其出现的每层断链。

时间与空间 ​

节点指针数期望为 $\sum _{k\ge 0}{p}^k=1/(1-p)$，总期望空间 $O(n)$。反向观察搜索路径：每层期望经过 $1/p$ 个节点，最高非空层以高概率为 $O({\log }_{1/p}n)$；因此期望搜索 $O(\log n)$，并可由几何尾和并集界得到高概率高度界。

快车道例子 ​

底层存放全部时间戳；较高层只保留逐级抽样的时间戳。查询某一时刻先在稀疏层跨过大片区间，接近目标后下降到底层。这与给链表额外固定步长索引不同：随机高度使任何插入位置都不需要整体重排。

边界与接口 ​

这些不是最坏界；随机源退化或能观察结构的自适应对手可能制造更细的条件问题。工程实现常设最大层，截断概率分布后须重新写高度保证。范围报告先定位左端点再顺底层输出，成本是 $O(\log n+k)$，不能漏掉输出量 $k$。并发 skip list 的内存回收与线性化点是额外正确性问题，不由这里的顺序概率分析覆盖。

插入路径与尾界 ​

搜索时保存每层最后一个小于目标的节点 update$[\ell ]$。抽出新高度 $h$ 后，只在 $0,\dots ,h$ 层把 update 的 next 改指新节点，再让新节点指向原后继；因此每层有序链不变量局部保持。

对任意常数 $c>1$，存在高度至少 $c{\log }_{1/p}n$ 的节点概率至多

$$n{p}^{c{\log }_{1/p}n}=n^{1-c}.$$

这是对最高层的高概率界；完整搜索步数还需结合每层水平移动的几何尾，不能只由“高度低”一句推出。

一条搜索路径的账 ​

搜索键 37 时，指针可能依次经过“顶层右移到 24、下降、右移到 32、下降两层、右移到 35”。从目标位置反向看，每层向左跨过的节点数服从几何尾部，期望为 $1/p$；层数期望 $O({\log }_{1/p}n)$，两者相乘给出期望 $O(\log n)$。

高概率界还要控制最高塔。由并集界，

$$\text{Pr}[\underset{x}{max}H(x)\ge c{\log }_{1/p}n]\le n^{1-c}.$$

因此“期望对数”不是凭直觉来自平均高度，而是同时约束层数和每层水平步数。若实现给高度设硬上限，必须说明超过上限的概率或重建策略。

参考资料

• William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM, 1990.
• Michael Mitzenmacher, Eli Upfal, Probability and Computing, randomized data structures chapters.