通过O（logn）访问和O（logn）插入实现数据结构？

Question

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

Answer 1

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

这种树被称为order statistic trees，排名树木，树木柜台...

你可以找到一个实现here，另一个here。

请参阅Cormen，Leiserson，Rivest和Stein撰写的名为“Intorduction to Algorithms”的第14章“增加数据结构”。

Answer 2

如果您需要整数索引（与键相对），请查看rope或deque，这对于这些操作本质上是O（c）。对于关联数据结构，一个典型的散列表也将被分摊到O（c），而一个平衡树将是O（log（n））。