标签: skip-lists

不确定问题应该在这里还是在程序员(或其他一些SE网站)上,但我对平衡二叉树和可索引的跳过列表之间的相关差异感到好奇.问题出现在这个问题的背景下.来自维基百科:

跳过列表是一种概率数据结构,似乎可能取代平衡树作为许多应用程序选择的实现方法.跳过列表算法与平衡树具有相同的渐近预期时间界限,并且更简单,更快速并且使用更少的空间.

跳过列表的空间要求是否取决于层次结构的深度？并且二叉树不是更容易使用,至少对于搜索(在平衡BST中授予,插入和删除可能是棘手的)？跳过列表还有其他优点/缺点吗？

所以我读了一些关于跳过列表的内容，目前正在实施一个。但是到目前为止，我还没有真正了解一件事。为什么跳过列表是随机的？在所有来源中，我发现跳过列表使用随机数来决定项目将被插入的级别。不能计算最佳值吗？或者你不能说“每第四个项目”应该在上面的级别插入吗？

我知道跳过列表是一种排序的数据结构，但它可以有重复的元素吗？或者，如果您尝试插入一个已经存在的元素，它只会返回指向预先存在的元素的指针？

我需要一个非常快速(插入,删除,包含)高度并发列表,可以使用比较器/可比较进行排序.

现有的ConcurrentSkipListSet是理想的,如果它是一个列表而不是一个集合.我需要插入多个与数据结构相同的项.

我目前正在考虑使用LinkedDeque,如果我找不到更好的东西,但该结构比高争用的跳转列表慢得多.

有什么建议？

编辑:我真正需要的,最低限度,是使用compareTo排序的东西,可以同时插入并可以使用对象标识删除/获取项目.注释中提到的所有其他并发要求仍然适用.

在中redis.h，skipnode的定义如下：

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

var span是什么意思？此var存储什么？

我开始研究ConcurrentSkipListSet.

从一开始我就试着了解SkipList是什么？

我想象它(可能的变种):

我有两个问题:

1. SkipList如何与并发相关联？
2. 为什么exis不是这种数据结构的并发变体？

我想知道如何在python中实现跳过列表.

我已经制作了一个链表但是我在如何创建链表的不同级别以及如何在搜索或将节点插入列表时迭代列表的每个级别时遇到问题.