0

skip-list に関する William Pugh の論文を読んでいます。セクション初期化で、彼は次のように述べています。

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

彼が何を言っているのかわからない。私は彼が意味していると思います:各ノードの最大許容レベルをnとします。したがって、レベルnのヘッダーを作成します。最初のステップでは、ヘッダーの各レベルが NIL を指します。それはそうです？

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

よろしくお願いします

MC

4

2 に答える 2

1

ドキュメントを読むことはできませんが、正しく思い出すと、それNILはリスト内の要素であり、それが常に最後の項目であることを保証するためにlevel有効な要素よりも大きい. levelあなたのレベルが から1になったとしましょう。その場合、のレベルを に3設定します。新しいスキップ リストを作成すると、次のようになります。NIL4

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|
于 2012-04-30T10:06:34.587 に答える
1

空のリスト (新しいリスト) にはレベル 1 が必要です。挿入中に必要に応じてさらにレベルが追加されます (これは後で行います)。

于 2012-04-30T10:11:32.023 に答える