寻找有效的间隔树算法

Question

我有一组对象，它们存储由低值和高值给定的间隔。我正在搜索数据结构，这将使我能够实时获取间隔与给定点重叠的所有对象。我还需要能够尽快添加和删除单个对象。基于红黑树的Interval trees具有O（log n）插入和删除时间以及O（n）空间。但是查找所有重叠的查询需要O（k log n）时间，如果重叠间隔很多，这可能比蛮力搜索更糟。有更好的方法吗？

Answer 1

为此工作​​制作了间隔树。找到与一个点重叠的所有间隔需要O（k + log n）时间，而不是O（k log n）。

这是您的维基百科链接中提到的“居中间隔树”。基于红黑树来实现其中之一是合理的：

• 主树将是一棵红黑树。每个节点都有其中心点和间隔列表。每当插入不与任何现有中心点重叠的新间隔时，便会创建一个新节点。每当删除节点的所有中心点重叠间隔时，就删除该节点。
• 为了平衡RB树而执行的旋转操作将需要将一些中心点重叠的间隔从子节点向上移动到其新的父节点。每个节点应将其中心点重叠间隔列表存储在其他红黑树中，以便可以在log（n）时间内完成此移动。请注意，RB树在每次插入/删除操作中均摊销固定的转数。

但是...因为您似乎已经使用RB树完成了[[not，并且RB树很复杂，所以我建议使用挖角执行相同的操作：https://en.wikipedia.org/wiki/Treap

陷阱比RB树要容易得多，因为它们从一开始就更简单，并且不需要旋转就可以使它们保持平衡，这使得维护中心点重叠间隔的列表变得容易得多。这些间隔也可以存储在挖方中。

容易得多...但仍然不那么容易：-）