在o（logk）的跳过列表中搜索 [英] search at skip list at o(logk)

问题描述

我需要编写一个在跳过列表中找到元素x的代码。我需要在O（logk）预期的运行时间中实现它，其中k是列表中x的位置（即，列表中的x之前有k-1个元素）。



我知道怎么做o（logn），但不是o（logk）。



你能给我指路吗？我只需要一般描述或伪代码，不能超过这个。

I need to write a code that finds element x in a skip list. I need to implement that in O(logk) expected running time, where k is the location of x at the list (i.e., there are k-1 elements before x in the list).

I know how to do it at o(logn), but not o(logk).

can you show me the way? I need only general description or pseudo code, not more than that.

推荐答案

你可以使用手指搜索算法。它具有所需的运行时间，因为它在跳过列表的最深层的两个节点处开始和结束。该算法的一种变体在文章 a Efficient Representation of a a C ++中的Semigroup [ ^ ]，请参见图1。



一般来说，注意水平链接的B +树比跳过列表更好，因为它们是确定性的数据结构。除此之外，如果您打算在实际应用中使用它们，我建议测量两种算法（自上而下和手指搜索）的性能。



问候，

Vadim Stadnik

You can use finger search algorithm. It has the required running time, since it starts and ends at two nodes at the deepest level of a skip list. A variant of this algorithm is described and available in the article Efficient Representation of a Semigroup in C++[^], see Figure 1 for its illustration.

In general, note that level-linked B+ trees are better choice than skip lists, since they are deterministic data structures. In addition to this, I suggest measuring performance of both algorithms (top-down and finger search), if you are planning to use them in practical applications.

Regards,
Vadim Stadnik

这篇关于在o（logk）的跳过列表中搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！