2

私は本当にこのリストの確率のことを理解していません. 「n/2 + 1 個以下のノードを検査する必要がある」というステートメントに加えて (n はリストの長さ)。 + 2 つのノードを調べる". この声明は、次のリンクで読みました: ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

4

4 に答える 4

3

あなたが理解していないのは、すべてのノードがレベル 1 でリンクを持っているということです。つまり、最下位レベルでは、データ構造は本質的にリンクされたリストです。これを使用してノードを検索することは、もちろん O(n) 操作です。

スキップ リストの各ノードには、少なくとも1 つのリンク (レベル 1 のリンク) があります。平均して、ノードの半分にはレベル 2 のリンクもあります。これがリンクが存在する最高レベルである場合、 O(n/2) の任意のノード。基本的に、探している項目が見つかるか、探している値よりも大きな値を持つノードに到達するまで、第 2 レベルのノードをたどります。その時点で、レベル 1 のノードに降りて、前のノード (つまり、探しているノードよりも小さいノード) から前方に検索します。

ここでも平均して、ノードの 1/4 にレベル 3 のリンクがあります。これらを使用すると、O(n/4) で任意のノードを見つけることができます。最初にレベル 3 のノードを、ノードが見つかるか通過するまで検索し、その時点からレベル 2 のノードにドロップダウンし、レベル 2 のノードが見つからない場合はレベル 1 のノードにドロップダウンします。

数学に従うと、最大レベルがmの場合、スキップ リスト内のノードが 未満である限り2^m、償却平均検索時間は O(log2(n)) になることがわかりnます。リスト内のアイテム。

したがって、スキップ リスト ノードの構造は次のようになります。

SkiplistNode
{
    int level;
    SomeType data; // the data held in the node
    SkiplistNode* forwards[]; // an array of 'level' forward references
}

ノードの値が 1 の場合、配列levelには 1 つの項目しかありません。forwardsレベル 4 の場合、レベル 4、3、2、および 1 のそれぞれに 1 つずつ、合計 4 つのエントリがあります。

結局のところ、配列の平均サイズは 2 です。これは進行に従います。forwards1 + 1/2 + 1/4 + 1/8 + 1/16, + 1/32, ...

Every node has a link at level 1
1/2 of the nodes have a link at level 2
1/4 of the nodes have a link at level 3
1/8 of the nodes have a link at level 4
etc.

それは今より明確ですか？

于 2014-10-28T14:15:12.997 に答える
2

スキップ リストについては、ウィキペディアの記事で詳しく説明されています。データ構造自体について特定の質問がある場合は、遠慮なく質問してください。

于 2010-12-12T17:36:23.700 に答える
1

やや理解しやすい説明がここにあります: http://igoro.com/archive/skip-lists-are-fascinating/

于 2014-10-27T09:07:58.180 に答える
1

スキップ リストに関する MIT の講義: http://video.google.com/videoplay?docid=-6710586843601387849#

于 2010-12-12T17:57:55.143 に答える