跳表

跳表

思想：从一个简单列表开始，逐层向上折半地抽稀

结构

• Skiplist: List of Tower
• Tower: Vector of Brick
• Brick: Node with Hands，指向前后的两个 Tower

随机

Brick 数量逐层随机减半，$S_k$ 中每个关键码有 $p=\frac{1}{2}$ 概率在 $S_{k+1}$ 中也存在。 则 Tower 的高度服从几何分布，期望空间复杂度为 $O(n)$

插入

先进行查找，插入一个空塔，根据随机的原则让塔生长，每长高一层就重新找到左邻和右邻并进行更新。 生长次数服从几何分布，期望为 $2$ 次。 每个 Tower 的期望高度为 $O(1)$。

删除

先进行查找，接着由上到下将塔清空。

查找

每层优先右移，再下移。

复杂度

纵向跳转

塔高不低于 $k$ 的概率为 $p^k$，低于 $k$ 的概率为 $1-p^k$ $P(|S_k|=0)=(1-p^k{)}^n\ge 1-n\cdot p^k,P(|S_k|>0)\le n\cdot p^k$ 推论：跳转表高度是 $O(\log n)$ 的高度极大 结论：纵向跳转期望次数为 $O(\log n)$

横向跳转

观察发现，横向跳转到的 Brick 必然为塔顶。 假设此时在第 $i$ 层，跳转次数最多的情况下，对于每次横向跳转，相当于看后继的 Tower 是否有第 $i+1$ 层（此时已知后继的 Tower 至少有 $i$ 层），若有，停止搜索并向下一层，若没有，横向跳转一次。 因此每一层中的横向跳转次数 $Y$ 服从几何分布，$P(Y=k)=(1-p{)}^k\cdot p$，有 $E(Y)=(1-p)/p=1$ 次，共有期望意义下 $O(\log n)$ 层，因此横向跳转总次数的期望为 $O(\log n)$ 次。

综上，跳表的查询的期望时间复杂度为 $O(\log n)$。