data-structures - skiplist-我真的需要一个解释，它是如何插入和删除的

Question

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

Answer 1

您没有理解的是，每个 节点在第 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.

现在更清楚了吗？