algorithm - 为什么不使用替代元素作为跳过列表中的垂直搜索节点？

Question

在我见过的大多数跳跃列表实现中，它们使用随机算法来决定是否必须将元素复制到上层。

但我认为在每个级别使用奇数索引元素以在上层具有副本会给我们带来对数搜索的复杂性。为什么不使用它？

例如: 数据:1 2 3 4 5 6 7 8 9

跳过列表:

1--------------------

1--------------------9

1--------5------------9

1----3----5----7----9

1-2-3-4-5-6-7-8-9

Answer 1

未使用它是因为它在从头构建列表时易于维护 - 但是当您向现有列表添加/删除元素时会发生什么？以前是奇数索引的元素现在是偶数索引，反之亦然。

在您的示例中，假设您现在添加 3.5，所有这些都是为了按照您描述的方式维护 DS，这将需要 O(k + k/2 + k/4 + ... ) 更改为DS，其中 k 是您刚刚插入的元素之后的元素数。

这基本上为您提供 O(n/2 + n/4 + ...) = O(n) 平均添加/删除复杂性。