确定性跳过列表自上而下插入中的违规

Question

假设我有一个跳跃列表，顺序是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，它会在插入到Head和150之间之前提升节点100的级别，并在100之前插入50。现在将发生冲突，因为在100和150之间没有节点，而在该间隙中应该至少有一个高度为h-1的节点作为minlimit=1。

我做错了什么？

Answer 1

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

你为什么要这么做？

根据你的链接，我找到的第一个关于确定性的1-2跳过列表(this paper)的参考资料(PDF)是这样的：

在...中注明，插入在...中可以自上而下地执行，...采用这种方法，当搜索要插入的元素时，我们通过将大小为3的任何间隙分成两个大小为1的间隙来在1-2-3跳过列表中插入元素。我们以这种方式确保结构在插入元素或不插入元素时保持间隙不变。

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

根据这个，你应该从级别3开始，然后看看下面的级别2。这里没有3个相同高度的节点-只有单个节点150 -所以你不需要提高任何东西。现在，下降到间隙头部的level 2,150。

这开始解决你的困惑了吗？

Answer 2

如果我想通过自顶向下的插入算法插入50，它会在进入

和150之间的空隙之前提升节点100的水平，并在100之前插入50。

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

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

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