在C++中实现Skip List

Question

[解决了]

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

我很确定我很清楚它是如何工作的.当您插入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,则值为"level up",如果为0,则插入结束.这是不正确的？
4. 如何存储类似于-infinite的值？

编辑:我已经开始编写一些代码,我正在考虑如何处理List构造函数....我猜测它的构造,"-infinite"值应存储在vectorname [0]元素中,我可以只需在创建后调用insert就可以将x放在适当的位置.

Answer 1

1. 只存储2个指针。在节点类中，一种在上面调用，一种在下面调用。
2. 不明白你的意思。
3. 根据维基百科，您还可以进行几何分布。我不确定分布类型对于完全随机访问是否重要，但如果您知道您的访问模式，这显然很重要。
4. 我不确定你的意思。您可以用浮点数表示类似的东西。