我知道跳表是一种排序数据结构，但它是否可以有重复元素？或者说如果你尝试插入一个已经存在的元素，它会返回指向已存在元素的指针？
跳表可以有重复元素吗？
6
- Austin
1
1它可以...请参见http://www.cs.yorku.ca/~ruppert/Mikhail.pdf - clarasoft-it
1个回答
5
答案是“可以，跳表可以有重复元素，但不是必需的。”
你可以创建一个支持重复元素的跳表。只需更新插入过程，如果找到要插入的元素，则直接在其后插入该元素。这类似于如何有BST存储多个相等值-当它找到相等元素时，插入过程总是向左或向右走。
但是，跳表是否必须始终允许重复？不需要，与并非所有BST均允许重复一样。
如果您在使用跳表库，请查阅文档以了解其是否支持重复项。如果您正在创建自己的跳表，请随意按照您喜欢的方式构建，并记录决策。
你可以创建一个支持重复元素的跳表。只需更新插入过程，如果找到要插入的元素，则直接在其后插入该元素。这类似于如何有BST存储多个相等值-当它找到相等元素时，插入过程总是向左或向右走。
但是，跳表是否必须始终允许重复？不需要，与并非所有BST均允许重复一样。
如果您在使用跳表库，请查阅文档以了解其是否支持重复项。如果您正在创建自己的跳表，请随意按照您喜欢的方式构建，并记录决策。
- templatetypedef
3
我的一些经验笔记：我实现了一个可索引的跳表，其中包含重复项（对于我的用例绝对需要这两个属性），但是对于具有大量重复项的数据集，性能问题很严重，因为链接没有跳过太多。我尝试过不在相等值的节点之间创建链接，但似乎并没有什么帮助。我仍在研究如何使其更快，我有很多想法，包括添加一个额外的指针，以便在最后一行上访问值的最后一次出现，以跳过所有重复项。 - Dici
另一个未经测试的想法：尝试在节点包含的距离值中表示重复项的数量（用于实现随机访问），并实际上仅插入一次值，只会增加或减少距离。 - Dici
更新：我提到的第二个想法是最好的。我成功地实现了相当快速（比
TreeSet中等效方法慢1到4倍，但具有随机访问和重复支持）的插入、删除和随机访问。我的实现在这里，供您参考：https://github.com/Dicee/algorithmicProblems/blob/master/hackerrank/algorithms/sorting/fraudulentActivityNotifications/SkipListSolutionForFun.scala - Dici网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接