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)平均添加/删除复杂性。

Answer 2

因为如果您开始删除节点或在中间插入节点，则结构很快需要重新平衡，否则它会失去访问和更新的对数保证。

实际上，有一个与您建议的结构非常相似的结构，即区间树，它通过不使用实际元素作为中间节点标签来解决更新问题。它也可能需要一些小心才能获得良好的性能。