Java中的跳表

Question

Java中的跳表

5

我在Java数据结构的Skip List主题下学习时发现以下内容：

在包含n个节点的Skip列表中，对于每个数字k和i，满足1≤k≤lg n且1≤i≤n/2k–1⎦ – 1，位于位置2k–1 · i的节点指向位于位置2k–1 · (i + 1)的节点。这意味着每隔两个节点指向它后面第二个节点，每隔四个节点指向它后面第四个节点，以此类推。如图3.17a所示。通过在列表上具有不同数量的引用字段的节点上实现：一半的节点只有一个引用字段，四分之一的节点具有两个引用字段，八分之一的节点具有三个引用字段，等等。引用字段的数量表示每个节点的级别，级别数为maxLevel = ⎣lg n⎦ + 1。

下图是：具有（a）均匀间距和（b）不均匀间距和不同级别节点的Skip列表；（c）显然显示参考节点的跳过列表。

我不明白其中的数学部分，也不理解什么是Skip List以及什么是偶数节点。

- xyz

2

它类似于SortedMap。您可以在O(log(n))时间内在其中找到一个值。通常，它的内存占用量与TreeMap相似或更小，但我猜由于其数组长度的变化，它的内存局部性可能更差。 - Gábor Bakos

1

@GáborBakos，我不同意你的观点。只有在进行O(n)操作来平衡它的情况下，才能实现O(log(n))，否则O(log(n))只是期望查找，而不是最坏情况。 - Ordous

@xyz 顺便问一下，你有没有尝试过维基百科上的“跳跃表”文章？它似乎比你读的那个东西写得更好。 - Ordous

@Ordous 感谢您的纠正，您是正确的，O(log(n)) 只是期望时间复杂度，而不是最坏情况。 - Gábor Bakos

@Ordous 还没有。我正在阅读Adam Drozdek的《Java数据结构与算法》这本书。 - xyz

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dharam · Accepted Answer

好的，让我试着让您理解这个。

跳表是一种数据结构，它可以在给定元素列表中使您的搜索更快。

一个更好的比喻是任何大城市的地铁网络。假设有90个站点需要覆盖，并且有不同的线路（绿色、黄色和蓝色）。

绿线仅连接编号为0、30、60和90的站点黄线连接0、10、20、30、40、50、60、70、80和90的所有站点蓝线连接从0到90的所有车站。

如果您想在0站上车并在75站下车，最佳策略是什么？

常识会建议您在0站乘坐绿线列车，在60站下车。在60站乘坐黄线列车，在70站下车。在70站乘坐蓝线列车，在75站下车。

其他任何方法都会更耗时。

现在将车站替换为节点，将线路替换为三个单独的列表（这些列表的集合称为跳表）。

只需想象一下，您想要在包含值为75的节点中搜索元素。

我希望这解释了什么是跳表以及它们如何高效。

在传统的搜索方法中，您可能会访问每个节点并在75个跳跃中到达75。在二进制搜索的情况下，您会在logN中完成。在跳表中，您可以在我们特定情况下进行1 + 1 + 15的相同操作。您可以计算一下，虽然看起来很简单：）

编辑：均匀间隔的节点和不均匀间隔的节点如您所见，我的比喻中，在每个线路的每个节点之间有相等数量的车站。这是均匀间隔的节点。这是一个理想的情况。

为了更好地理解它，我们需要了解跳表的创建。

在其构建的早期阶段，只有一个列表（蓝线），并且每个新节点首先添加到适当位置的列表中。当蓝线中的节点数增加时，就需要创建另一个列表（黄线）并将其中一个节点提升到列表2中。（PS：列表1的第一个和最后一个元素始终被提升到跳表集中新添加的列表中）。因此，一旦添加了新列表，它将具有三个节点。

晋升策略：如何找出要从最底部的列表（蓝线）晋升到上层列表（黄线和绿线）的节点。

最好的方法是随机的:)因此，假设在添加新节点时，我们掷硬币以查看它是否可以晋升到第二个列表。如果是，则将其添加到第二个列表中，然后再次掷硬币以检查是否必须将其添加到第三个列表中。

所以，使用这种随机机制时，可能存在节点间距不均匀的情况。 :) 希望这能帮助您。

蓝色、黄色、绿色火车的图表，从0乘坐蓝色火车到60，从60乘坐黄色火车到70，最后从70乘坐蓝色火车到71、72、73、74和75。