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