algorithm - 是否存在表示主要操作时间为 O(n*log n) 的有序列表的数据结构？

Question

我正在寻找一种数据结构，允许以 O(n*log(n)) 复杂度解决特定问题。它需要表示一组整数，我可以在其中执行以下操作:- 添加一个元素- 检查集合中是否存在元素- 删除大于给定整数的每个值希望具有对数复杂度。

我寻找链表，因为在中间添加一个元素并删除整个结构的一部分很容易，但我不知道如何保持有序列表或实现二分法搜索。起初我在考虑哈希表，但我不知道如何过滤集合。我正在查看平衡二叉树，但我不知道我是否在寻找某种错觉，或者它是否以某种方式存在，但我就是找不到。

Answer 1

为了从头开始实现，我建议使用 Treap .

Treap 只是一棵二叉搜索树，其中每个节点都被赋予随机优先级，并且它作为树满足堆条件。这种随机数据结构使得查找、插入、删除和拆分树的预期时间为 O(log(n))。前三个相当简单。要拆分，只需将一个节点放在要拆分的点上，其优先级高于根节点。然后一半在该节点的一侧结束，另一半在另一侧结束。

请注意，虽然拆分是 O(log(n))，但释放删除的位是 O(n)。

请注意，您可能不必执行任何操作。例如，在 C++ 中，您可以只使用 std::map。除了删除之外，这些操作的性能都是O(log(n))。从大小为 n 的结构中删除长度为 m 的范围是 O(m + log(n))。如果您考虑有关释放内存的评论，那就太理想了。