插入跳过列表

Question

A 跳过列表是一种数据结构，其中元素按排序顺序存储，并且列表中的每个节点可以包含多于1个指针，并用于减少搜索所需的时间从单一链接列表中的O(n)到平均情况的O(lg n)的操作。它看起来像这样：

参考：由沃伊切赫·穆拉 “跳表” - 自己的工作。通过维基共享资源，根据公有领域授权 - http://commons.wikimedia.org/wiki/File:Skip_list.svg#mediaviewer/File:Skip_list.svg

它可以被看作是一个类比标尺：

在跳跃列表，搜索一个元素，删除一个是好的，但是当它来插入，它变得困难，因为根据Data Structures and Algorithms in C++: 2nd edition by Adam Drozdek：

要插入一个新元素，只是插入必须被重组节点以下的所有节点;指针的数量和指针的值必须改变。

---

我可以从这个诠释，虽然选择基于节点的可能性指针的随机数一个节点插入一个新的元素，不创建一个完美的跳跃列表，它变得非常接近它在考虑大量元素时（例如〜900万）。

我的问题是：为什么我们不能在新节点中插入新元素，根据前一个节点确定它的指针数量，将它附加到列表末尾，然后使用高效的排序算法仅对存在于节点中的数据进行排序，从而保持跳过列表的完美结构并且还实现了插入复杂性？

编辑：我还没有尝试过任何代码，我只是提出了一个观点。仅仅因为实施跳过列表有点困难。抱歉。

Answer 1

您在这一点上有问题and then use efficient sorting algorithms to sort just the data present in the nodes。对数据进行排序将具有复杂性O(n*lg(n))，因此会增加插入的复杂性。从理论上讲，您可以为插入的每个节点选择“完美”数量的链接，但即使这样做，当您执行删除操作时，完美性也会“破碎”。使用随机化的方法足够接近完美的结构来表现良好。

Answer 2

您需要有搜索位置的功能/方法。

它需要做以下几点：

1. 如果插入的唯一密钥，它需要找到节点。那么你保留一切，只需更改数据（行李）。例如node-> data = data。

2. 如果您允许重复，或者如果找不到密钥，那么此函数/方法需要为每个高度（通道）提供前一个节点。然后确定新节点的高度并将其插入找到的节点之后。

这里是我的C++实现： https://github.com/nmmmnu/HM2/blob/master/hm_skiplist.c

您需要检查以下功能：

static const hm_skiplist_node_t *_hm_skiplist_locate(const hm_skiplist_t *l, const char *key, int complete_evaluation); 

它存储hm_skiplist_t结构中的位置。

complete_evaluation用于节省时间以防万一您需要数据并且您不打算插入/删除。

Answer 3

插入节点时不需要修改任何后续节点。详情请参阅原稿Skip Lists: A Probabilistic Alternative to Balanced Trees。

我已经实现了该引用的跳过列表，并且我可以向您保证我的插入和删除例程不会修改插入点前面的任何节点。

我还没有读过你指的那本书，但是出于上下文的考虑，你突出显示的这段文字是错误的。