问题标签 [skip-lists]

我想知道这里是否有人曾经使用过跳过列表。它看起来与平衡二叉树具有大致相同的优势，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库（如果有，它的名称是什么）？

我最近遇到了一种称为跳过列表的数据结构。它似乎与二叉搜索树具有非常相似的行为。

为什么要在二叉搜索树上使用跳过列表？

[解决了]

所以我决定尝试创建一个排序的双向链接跳过列表......

我很确定我很好地掌握了它的工作原理。当您插入 x 时，程序会在基本列表中搜索放置 x 的适当位置（因为它已排序），（从概念上讲）掷硬币，如果“硬币”落在 a 上，则该元素将添加到其上方的列表中（或创建一个新列表，其中包含元素），链接到它下面的元素，然后再次翻转硬币，等等。如果“硬币”在任何时候落在 b 上，则插入结束。您还必须在每个列表中存储一个 -infinite 作为起点，这样就不可能插入小于起点的值（意味着永远找不到它。）

要搜索 x，请从“左上角”（最高列表最低值）开始，然后“向右移动”到下一个元素。如果值小于 x，则继续下一个元素，依此类推，直到“走得太远”并且值大于 x。在这种情况下，您返回最后一个元素并向下移动一个级别，继续此链直到您找到 x 或永远找不到 x。

要删除 x，您只需搜索 x 并在每次出现在列表中时将其删除。

现在，我只是简单地制作一个存储数字的跳过列表。我认为 STL 中没有任何东西可以帮助我，所以我需要创建一个类 List，它包含一个整数值并具有成员函数、搜索、删除和插入。

我遇到的问题是处理链接。我很确定我可以创建一个类来处理带有指向前一个元素和前面元素的指针的“水平”链接，但我不确定如何处理“垂直”链接（指向相应的元素在其他列表中？）

如果我的任何逻辑有缺陷，请告诉我，但我的主要问题是：

1. 如何处理垂直链接以及我的链接思路是否正确
2. 现在我阅读了我的类 List 想法，我认为 List 应该包含一个整数向量而不是单个整数。事实上，我很积极，但只是想要一些验证。
3. 我假设硬币翻转将简单地调用 int 函数，其中 rand()%2 返回值 0 或 1，如果为 0，则值“升级”，如果为 0，则插入结束。这是不正确的吗？
4. 如何存储类似于-infinite的值？

编辑：我已经开始编写一些代码并正在考虑如何处理 List 构造函数......我猜在它的构造上，“-infinite”值应该存储在 vectorname[0] 元素中，我可以只需在创建后对其调用 insert 以将 x 放在适当的位置。

我在从跳过列表中删除节点时遇到了一些问题。我有以下结构：

我认为问题在于搜索具有给定值的节点然后将其删除的函数。该功能是这样实现的：

该函数可以正常工作，但是如果我取消注释两条注释行，列表似乎会中断。通过中断，我的意思是以下测试代码永远不会完成：

问题在于在for列表中插入更多值的最后一个循环。如果这两行被注释掉，程序将在大约 10 秒内完成。如果我取消注释它们，它似乎进入了一个无限循环，因为它甚至没有在几分钟内完成。我不确定这是否是从跳过列表中删除节点的正确方法，所以我也发布了我的插入函数：

所以，我的问题是：

1. 为什么程序会中断，以及如何在实际删除要从内存中删除的节点时使其工作？
2. 这是实现跳过列表的正确方法，还是我使用了错误的方法？

我需要实现一个无锁跳过列表。我试图寻找文件。不幸的是，我发现的只是无锁单链表（有多种形式）。但是如何实现无锁跳过列表呢？

大家好，我是新人，所以我相信你会帮助我在跳过列表时遇到一些麻烦这里是代码

我编译得很好但是当我运行执行它突然停止工作请帮助我

我最近一直在阅读有关跳过列表的内容。

我有一个针对静态数据集执行相当复杂的 Sql 查询的 Web 应用程序。

我想实现一个缓存系统，从而生成 sql 查询的 md5 哈希，然后返回查询的缓存数据集（如果它存在于集合中）。

哪种算法会更好，Dictionary 还是 SkipList？为什么？

http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4

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

我正在阅读有关跳过指针的内容，有人建议最好放置均匀间隔的 sqrt(len of list) 跳过指针。有人能告诉我这里的“均匀分布”是什么意思吗？我也想看看用 Java 或 Python 做这样的事情的代码

我需要一个列表类型的数据结构来在项目中实现。实际上它不一定是某种列表，但它必须很快，我将使用它来不断地插入/删除/检索数据（其他数据结构）。我可能会插入一些东西，搜索，再次插入，删除，再次搜索等等，所以动作是随机的。

到目前为止，我发现跳过列表最快，还有什么比这更快？