2

我真的不明白这个列表的概率。除了语句“我们必须检查不超过 n/2 + 1 个节点（其中 n 是列表的长度）。另外给每四个节点一个指针前四位（图 1c）要求不超过 n/4 + 2 个节点被检查”。我在以下链接中阅读了此声明：ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

4

4 回答 4

3

你不明白的是，每个节点在第 1 层都有一个链接。也就是说，在最低层，数据结构本质上是一个链表。使用它搜索节点当然是 O(n) 操作。

跳过列表的每个节点至少有一个链接：第 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
}

如果一个节点的level值为 1，那么forwards数组中将只有一项。如果它位于第 4 级，则将有四个条目：第 4、3、2 和 1 级各有一个。

事实证明，数组的平均大小forwards为 2。这遵循级数1 + 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

跳过列表在他们的Wikipedia 文章中得到了很好的解释。如果您对数据结构本身有特定的问题，请随时问他们。

于 2010-12-12T17:36:23.700 回答
1

麻省理工学院关于跳过列表的讲座：http: //video.google.com/videoplay ?docid=-6710586843601387849#

于 2010-12-12T17:57:55.143 回答
1

可以在这里找到更容易理解的解释：http: //igoro.com/archive/skip-lists-are-fascinating/

于 2014-10-27T09:07:58.180 回答