我有一组对象，用于存储由低值和高值给出的间隔。我正在寻找一种数据结构，它允许我实时获取其间隔与给定点重叠的所有对象。我还需要能够尽快添加和删除单个对象。 Interval trees基于红黑树的插入和删除时间为 O(log n)，空间为 O(n)。但是查找所有重叠的查询需要 O(k log n) 时间，如果存在许多重叠间隔，这可能比暴力搜索更糟糕。有更好的方法吗？
最佳答案
区间树就是为此工作而制作的。查找与某个点重叠的所有区间需要 O(k + log n) 时间，而不是 O(k log n)。
这是维基百科链接中提到的“中心间隔树”。基于红黑树实现其中之一是合理的:
- 主树是一棵红黑树。每个节点都有其中心点和间隔列表。每当插入不与任何现有中心点重叠的新间隔时，都会创建一个新节点。每当您删除节点的所有中心点重叠间隔时，您就删除了该节点。
- 为平衡 RB 树而执行的旋转操作将要求您将一些中心点重叠间隔从子节点向上移动到其新父节点。每个节点应将其中心点重叠间隔列表存储在其他红黑树中，以便可以在 log(n) 时间内完成此移动。请注意，RB 树每次插入/删除都会进行摊销常数旋转次数。
但是...由于您似乎尚未使用 RB 树完成此操作，并且 RB 树很复杂，因此我建议使用 treap 执行相同的操作:https://en.wikipedia.org/wiki/Treap
Treaps 比 RB 树容易得多，因为它们一开始就更简单，并且不需要旋转来保持平衡，这使得维护中心点重叠间隔列表变得更加容易。这些间隔也可以存储在treaps中。
容易多了...但仍然没那么容易:-)
关于algorithm - 寻找高效的区间树算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60170209/