data-structures - 跳过列表是如何初始化的？

Question

我正在阅读William Pugh 关于 skip-list 的论文。在初始化部分他说：

一个元素 NIL 被赋予一个大于任何合法键的键。所有跳过列表的所有级别都以 NIL 终止。初始化一个新列表，使列表的级别等于 1，并且列表头的所有前向指针都指向 NIL。

我不确定他说什么。我认为他的意思是：让n为每个节点的最大允许级别。因此，构建一个级别为n的标题。在第一步中，标题的每一级都指向 NIL。这是正确的？

现在，当第一个节点到达时，它将以概率的方式插入，因此它的级别应该是不可预测的。为什么他谈到 1 级列表？我错过了什么？

此致

MC

score 1 · Accepted Answer

我无法阅读该文档，但如果我没记错的话，那将NIL是列表中的一个元素，并且它level大于任何有效值level，以确保它始终是最后一项。假设您的级别从1到3，那么您将NIL' 级别设置为4。当您创建一个新的跳过列表时，它应该如下所示：

H = Header
N = Nil
   _    _
4 |H|->|N| 
3 |H|->|N| <- max for normal elements
2 |H|->|N|
1 |H|->|N|

添加一些元素后，您将拥有：

   _                   _
4 |H|---------------->|N| 
3 |H|-------|B|------>|N|
2 |H|-------|B|->|C|->|N|
1 |H|->|A|->|B|->|C|->|N|

score 1 · Accepted Answer

空列表（一个新列表）应该有级别 1。在插入过程中根据需要添加更多级别（稍后会出现）。

2 回答 2