O(logn)访问和O(logn)插入的数据结构的实现？

Question

有没有人知道一种数据结构，在这种数据结构中，我可以在最坏情况下O(logn)中访问和删除第k项，并且还支持在最坏情况下O(logn)中的第k项之后插入一项的操作？

Answer 1

是。您所描述的内容可以通过扩展树来实现。每个节点都有一个计数器，指示其子树(包括其自身)中的节点数。对于叶子节点，计数器是1。对于根节点，计数器是节点总数。这样，您就可以通过从根开始的二进制搜索找到第k个项目。无论何时插入/删除元素，都必须更新从该位置到根的路径中的计数器。

这种树被称为order statistic trees树、等级树、计数器树……

您可以找到一个实现here和另一个here。

请参阅由Cormen，Leiserson，Rivest和Stein撰写的“算法归纳”一书中的第14章“增强数据结构”。

Answer 2

如果您需要整数索引(而不是键)，请看一下rope或deque，对于这些操作，它们基本上是O(c)。

对于关联数据结构，典型的哈希表也将被摊销为O(c)，而平衡树将被摊销为O(log(n))。