我在这个主题下浏览了java中的数据结构，Skip list我遇到了以下问题：
在 , 的跳过列表中n nodes，对于每个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) 不均匀分布的不同层级节点的跳过列表；(c) 清晰显示参考节点的跳过列表。
我不明白数学部分以及 sktip 列表甚至节点到底是什么？
好的，让我试着让你理解这一点。
跳过列表是一种数据结构，它肯定会使您在给定元素列表中的搜索速度更快。
一个更好的类比是任何大城市的地铁网络。想象一下有 90 个车站要覆盖，并且有不同的线路（绿色、黄色和蓝色）。
绿线仅连接编号为 0、30、60 和 90 的车站黄线连接 0、10、20、30、40、50、60、70、80 和 90 蓝线连接从 0 到 90 的所有车站。
如果你想在 0 站上车，想在 75 下车，最好的策略是什么？
常识会建议从0号站搭乘绿线的火车，在60号站下车。从60号站搭乘另一辆黄线的火车，在70号站下车。从70号站搭乘另一辆蓝线的火车，在70号站下车。 75.
任何其他方式都会更耗时。
现在用三个单独的列表（这些列表的集合称为跳过列表）用节点和线替换站。
并且只是想象您想在包含值 75 的节点处搜索元素。
我希望这能解释什么是跳过列表以及它们的效率。
在传统的搜索方法中，您可以访问每个节点并在 75 跳中到达 75。在二进制搜索的情况下，您可以在 logN 中完成。在跳过列表中，在我们的特定情况下，您可以在 1 + 1 + 15 中执行相同的操作。你可以做数学，虽然看起来很简单:)
编辑：均匀间隔的节点和不均匀间隔的节点 正如你所看到的我的类比，它在每条线上的每个节点之间具有相同数量的站点。这是均匀分布的节点。这是一个理想的情况。
为了更好地理解它，我们需要了解跳过列表的创建。
在其构建的早期阶段，只有一个列表（蓝线），每个新节点首先在适当的位置添加到列表中。当蓝线中的节点数量增加时，需要创建另一个列表（黄线）并将其中一个节点提升到列表 2。（PS：列表 1 的第一个和最后一个元素总是提升到跳过列表集中新添加的列表）。因此，添加新列表的那一刻，它将具有三个节点。
提升策略：如何找出从最底部的列表（蓝线）到最上面的列表（黄线和绿线）提升哪个节点。
最好的决定方法是随机 :) 所以让我们说，在添加一个新节点时，我们掷硬币看它是否可以提升到第二个列表。如果是，那么我们将其添加到第二个列表中，然后再次掷硬币检查是否必须将其添加到第三个列表中。
所以你看，如果你使用这种随机机制，可能会出现节点间隔不均匀的情况。:)
希望这可以帮助。
