c++ - O(logn) 中 O(logn) 删除和索引访问的数据结构

Question

请推荐一个具有 O(logn) 删除的数据结构，我想要 O(1) 或 O(logn) 的数据结构中的元素索引？

Answer 1

大多数自平衡有序二叉树可以修改以保持每个节点中的子节点数量，并且在每次操作的 lg(n) 时间内保持这一点非常容易。

他们显然每次操作修改的节点少于 lg(n) 个节点，并且根据我的经验，他们修改的节点通常是“垂直相关的”。它不是免费的，但它往往不会很贵。 ¹

一旦您在树的节点中获得了该数据，n就很容易找到第 th 个元素（如果n在左子树中大于 #，则从左子树中减去 #n并递归到右子树，否则递归到未更改的左子树n）。

这也适用于非二元自平衡树，例如 B 树。

据我所知，没有std容器支持随机对数删除、插入和索引操作。我往后找了一个。我还快速检查了 boost，甚至查看了多索引容器，但找不到让它工作的方法。

脚注：

¹当您修改一棵树时，您希望在该节点处获得节点的子节点数量的成本为 O(1)，您必须修改从更改到根的节点。每个修改节点最多有 lg(n) 个。但是，如果节点彼此“垂直相关”，则您需要修复的节点在每个节点更改时几乎都是相同的。

另一方面，假设您的树再平衡算法以某种方式设法修改了 lg(n) 完全不相关的节点，那么维持计数的成本将高达 lg(n)*lg(n)。