数据结构中的跳过列表

在跳过列表中,只需从此点a继续进行搜索,即可从包含元素b的节点中手指搜索元素a。

注意,如果a <b,则搜索沿反向进行;如果a> b,则搜索沿向前进行。

向后的情况与跳过列表中的常规搜索对称,但向前的情况实际上更复杂。

通常,由于在列表开头的哨兵被认为是最高的节点,因此在跳过列表中的搜索预计会很快。

但是,我们的手指可能与一个高度为1的节点相关联。因此,我们在尝试搜索时可能很少攀爬;通常不会发生的事情。

跳过列表最重要的属性是它们需要预期的线性空间,包括预期的O(log n)级别,支持预期的O(log n)时间搜索,并支持预期O(1)中给定位置的插入和删除。 ) 时间。

它已经详细说明了跳过列表的各种属性和扩展,包括有关跳过列表如何在预期O(log d)时间内支持手指搜索的伪代码。为了便于向后手指搜索,将节点V的手指存储为预期的O(log n)空间手指数据结构,该结构针对每个级别i存储指向V左侧节点的指针,其中级别i指针要么指向V或V右边的节点。移动手指需要相应更新此指针列表。

通过首先识别手指数据结构中位于搜索关键字y左侧的最低节点来完成手指反向搜索,其中手指数据结构中的节点按级别递增的顺序考虑。

此后,搜索从标识的节点向下进行,类似于标准跳过列表搜索。