有没有一种排序的数据结构，可以在对数时间内进行插入、删除和查找（包括距离）？

Question

6

我有一个已排序的数组，使用二分查找(std::upper_bound)在O(logn)时间内找到小于特定值的项目数。
现在我想要在保持其排序的同时从该数组中插入和删除。我希望总体复杂度为O(logn)。

我知道可以使用二叉搜索树或std::multiset进行插入、删除和上界操作，但我无法以对数时间获取距离/索引(std::distance对于集合是O(n))。

那么有没有办法实现我想做的事情呢？

- CCD

请修改您的问题 - 数组本身是一种线性数据结构，因此插入或删除操作不会像您期望的那样便宜。 - Fei

根据数据的大小，排序数组受到连续性（友好缓存）的益处，因此如果您只是保持使用数组，在std::lower_bound/std::upper_bound告诉您插入/删除的位置，您可能会获得更好的性能。 - Galik

这不是建议问题的重复，而是寻求比O(n)索引/距离更好的解决方案。虽然我认为插入的要求与此相互矛盾。 - Galik

“n”的范围是多少，您应该存储哪些元素的值？ - Kunal Puri

范围为10^5，值从-10^9到10^9。 - CCD

2个回答

1

你可以使用平衡二叉搜索树，其中每个节点的左子树大小来计算距离。

- Prerna Jain

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ruakh · Accepted Answer

您可以通过在每个节点中包含一个“子树大小”数据成员（以及标准的“左孩子”，“右孩子”和“值”成员）来增强任何平衡二叉搜索树数据结构（例如红黑树）。然后，您可以在从根向下导航到该元素时计算小于给定元素的元素数量。

这会增加一些簿记工作，当然也意味着您需要使用自己的平衡二叉搜索树实现，而不是标准库中的实现。但它是完全可行的，并且不会影响任何操作的渐近复杂度。