4

假设给我一个跳过列表，顺序为 3。

           HEAD
level 3     |--------------------------------------------> X
            |                      |---|
level 2     | -------------------> |   | ----------------> X
            |    |---|    |---|    |---|    |---|
level 1     | -> |   | -> |   | -> |   | -> |   | -------> X
            |    |---|    |---|    |---|    |---|
            |    | 20|    |100|    |150|    |200|
            |    |---|    |---|    |---|    |---|


minlimit = ceil(order/2) - 1 = 1

maxlimit = order - 1 = 2

所以本质上它是一个1-2 skip-list.

如果我想50通过自上而下的插入算法插入，它会100在落入Headand150和 insert 50right before之间的间隙之前提高节点的级别100。现在将发生违规，因为 和 之间没有节点100，而在该间隙中150应该至少有一个高度为.h-1minlimit=1

我究竟做错了什么？

4

2 回答 2

2

如果我想通过自上而下的插入算法插入 50，它将在下降到 Head 和 150 之间的间隙之前提高节点 100 的级别，并在 100 之前插入 50

你为什么做这个？

我为确定性 1-2 跳过列表（本文）找到的第一个参考资料，根据您​​的链接可用（PDF）说：

如 [...] 中所述，在 ... 中的插入可以自上而下进行，... 采用这种方法，我们通过将任何大小为 3 的间隙分成两部分来在 1-2-3 跳过列表中插入一个元素搜索要插入的元素时，间隙大小为 1。我们以这种方式确保结构在有或没有插入元素的情况下保持间隙不变。

更准确地说，我们从标题开始搜索，并且在比跳过列表的高度高的级别 1 处。当我们找到要下降的间隙时，我们查看下面的级别，如果我们看到连续 3 个相同高度的节点，我们将中间的节点升起；之后我们下降一个级别。当我们到达底层时，我们只需插入一个高度为 1 的新节点。

据此，你应该从第 3 级开始，然后看下面的第 2 级。这里连续没有 3 个相同高度的节点 - 只有单个节点 150 - 所以你不需要提出任何东西。现在，下降到差距 [HEAD,150] 中的第 2 级。

这是否开始解决您的困惑？

于 2014-05-01T15:54:14.607 回答
2

如果我想通过自上而下的插入算法插入 50，它将在下降到 Head 和 150 之间的间隙之前提高节点 100 的级别，并在 100 之前插入 50。

它不会提高节点 100 的级别。而是会提高节点 20 的级别。根据算法，每当您到达maxlimit间隙中的节点时，您就会提高该间隙中ceil((maxlimit/2))th节点的级别。

在这种情况下，当节点 20 的级别提升到级别 2 时，头和节点 20 之间没有级别 1 节点，但不会导致任何结构违规。Munro 等人在论文中描述的确定性跳过列表的原始结构。这样读。

假设在 n 个元素的跳跃列表中存在一个高度为 1 的第 0 个和第 (n+1) 个节点，其高度比跳跃列表的高度高，我们要求在高度为 h (h > 1) 的任意两个节点之间或更高，则存在 1 或 2 个高度为 h – 1 的节点。

于 2014-05-02T19:11:07.897 回答