如果事先知道'n'（要存储的元素数量），我会说正确吗？
跳过列表的 Maxlevel 是(log n + 1)，因为我需要在创建跳过列表之前知道 maxlevel ，这意味着我应该知道要存储的元素数量是多少。
问问题
274 次
2 回答
1
你不需要在创建skiplist之前知道它的最大级别，只要你准备好动态调整head的大小，它的大小正好是maxlevel. 由于maxlevel是近似log N的，调整头部大小很少发生，当它发生时，它涉及的工作很少。如果您真的想避免这种情况，您最初可以创建一个容量足以容纳整个可用存储的磁头，尽管如果您的大多数跳过列表都是几百个元素，那将浪费空间。
这一切都有效，因为跳过列表的搜索过程永远不会向上移动。只有下来。所以插入一个比任何现有节点更高级别的新节点不需要修改任何现有节点，除了head，必须修改为指向新节点的最高级别。（否则，新的关卡将毫无用处。）
作为一个奇怪的实现细节，没有必要存储节点的大小；一个节点指向 level 的事实i足以证明该节点至少具有i级别，因此永远不需要i与节点的大小进行比较。只需要知道头部的大小。
于 2013-05-02T05:24:38.970 回答
0
maxlevel 可以动态增加。
用于maxlevel=2^(n-1)前 (2^n-1) 个节点。当第 2^n 个节点到来时，它被分配level=2^n，接下来的 2^n...2^(n+1) 个节点使用maxlevel=2^n.
于 2013-05-02T07:13:42.093 回答