跳过列表没有随机化？

Question

所以我读了一些关于跳过列表的内容，目前正在实施一个。 但有一件事我没有真正到目前为止。为什么跳过列表是随机的？在所有来源中，我发现跳过列表使用随机数字来决定该项目将插入的级别。 无法计算最佳值吗？或者你能不能在上面的层面上插入“每第四项”？

Answer 1

跳过列表可以确定性地构建，例如以最小化摊销访问成本。然而，对于任何确定性构造方法，高级列表条目的集合总是已知的，因此很容易构建一个“敌对”的删除操作集，将性能退化为O（n）。随机构造仍然存在一组最坏情况的删除，但是对于任何规模较大的列表，通过纯粹的机会发现最坏情况的删除序列的可能性是微乎其微的。