スキップリストはどのように初期化されますか？

Question

私はWilliam Pugh's paper about skip-listを読んでいます。セクション初期化で彼は言う：

NILはいかなる法的キーより大きいキーを与えている要素。すべてのスキップリストのすべてのレベル はNILで終了します。新しいリストは に初期化され、リストのレベルは1に等しく、リストのヘッダのすべての前方ポインタ はNILを指します。

私は彼の言うことをよく分かりません。私は彼が意味すると思います：n各ノードの最大許容レベル。レベルnのヘッダーを作成します。第1のステップでは、ヘッダの各レベルはNILを指し示す。それはそうです？

最初のノードが到着すると、これは確率的な方法で挿入されるため、そのレベルは予測できません。なぜ彼はレベル1のリストを話すのですか？私は何が欠けているのですか？

敬具

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を持っています。挿入中に必要に応じてレベルが追加されます（後で説明します）。