data-structures - 实现具有 O(logn) 访问和 O(logn) 插入的数据结构？

Question

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

Answer 1

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

这种树被称为顺序统计树、等级树、计数器树……

您可以在此处找到一个实现，在此处找到另一个实现。

请参阅 Cormen、Leiserson、Rivest 和 Stein 所著的伟大著作“算法导论”中的第 14 章“增强数据结构”。

Answer 2

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

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