如何初始化跳過列表？

Question

我在閱讀William Pugh's paper about skip-list。在部分初始化他說：

的元素NIL給出一個關鍵比任何法律鍵更大。所有跳過列表的所有級別 都以NIL結尾。新列表初始化爲 ，以便列表的級別等於1，並且列表頭部的所有前向指針 指向NIL。

我不確定他說什麼。我認爲他的意思是：設爲n每個節點的最大允許等級。所以建立一個級別爲的標題ñ。在第一步中，標題的每個級別指向NIL。這是正確的？

現在，當第一個節點到達時，這將以概率方式插入，因此其級別應該是不可預知的。爲什麼他談論一級列表？我錯過了什麼？

問候

MC

Answer 1

我無法讀取該文件，但如果我沒有記錯，這將會是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| 

Answer 2

空的列表（一個新的列表）應具有等級1.在插入期間根據需要添加更多等級（稍後）。