我正在寻找一种数据结构，允许以O(n*log(n))的复杂性解决特定问题。它需要表示一组整数，我可以在其中执行以下操作： - 添加元素 - 检查集合中是否存在元素 - 删除大于给定整数的每个值 希望具有对数复杂性。
我寻找链表，因为在中间添加一个元素并删除结构的整个部分很容易，但我不知道如何保持有序列表或实现二分搜索。起初我在考虑哈希表，但我不知道如何过滤集合。我正在看平衡的二叉树，我不知道我是否在寻找妄想的东西，或者它是否以某种方式存在，我只是找不到它。
为了从头开始实现，我建议使用 Treap。
Treap 只是一个二叉搜索树，其中每个节点都被赋予随机优先级，并且它作为树满足堆条件。 这种随机数据结构使得查找、插入、删除和拆分树的预期时间O(log(n))。 前三个相当简单。 要拆分，您只需在要拆分的点放置一个节点，其优先级高于根。 然后一半在该节点的一侧缠绕，另一半在另一侧缠绕。
请注意，虽然拆分O(log(n))，但释放已删除的位是O(n)。
请注意，您可能不必实现任何内容。 例如，在C++中，您可以只使用std::map。 除删除操作外，这些操作的性能O(log(n))。 从大小n的结构中删除长度m范围是O(m + log(n)). 如果您考虑有关释放内存的评论，那是理想的。