1

我试图了解跳过列表如何用于插入，但是当我将其绘制出来时，它不起作用。

|-inf<---------------------------->+inf|0
|-inf<--------->4<---------------->+inf|1
|-inf<--------->4<--->9<--->11<--->+inf|2
|-inf<--->1<--->4<--->9<--->11<--->+inf|3

所以我想在上面的链表上插入 5。

从第 0 行开始：从 -inf 开始，将 5 与 +inf 进行比较，移动到下一行。

移至第 1 行：

是 5 <= 4，不。比较右边的内容，+inf。从元素 4 向下移动到第 2 行。

移至第 2 行：

现在我们在 4 和 9 之间遍历，所以比较类似于 5 <= 4？不。是 5 <= 9 吗？是的。在 4 到 9 之间插入。

但是现在 5 没有出现在第 3 行？我究竟做错了什么？

4

1 回答 1

0

当您看到 5 <= 9 时，您必须继续向下直到到达底部。可能有 4 到 9 之间的任何数字仍然在较低级别之一中。当您确定其在底行中的位置时，将其插入那里，然后根据 RNG 的结果开始将其插入高一行。插入的完整序列类似于：

  1. 5 > +inf? 否：向下移动。
  2. 5 > 4？是：向右移动。
  3. 5 > +inf? 否：向下移动。
  4. 5 > 9？否：向下移动。
  5. 5 > 9？否：向下移动。
  6. 在上一步中无法向下移动，因此在底层插入 4 到 9 之间。
  7. 以概率方式将 5 添加到更高的行。
于 2016-05-14T17:07:30.307 回答