寻找一种有效的区间树算法
Looking for an efficient Interval tree Algorithm
我有一组对象，它们存储由低值和高值给出的间隔。我正在寻找一种数据结构，这将使我能够实时获取所有对象，其间隔与给定点重叠。我还需要能够尽快添加和删除单个对象。 Interval trees基于红黑树的插入和删除时间为O(log n)，O(n)space。但是查找所有重叠的查询需要 O(k log n) 时间，如果有很多重叠间隔，这可能比暴力搜索更糟糕。有更好的方法吗？
间隔树是为这项工作制作的。找到与一个点重叠的所有间隔需要 O(k + log n) 时间，而不是 O(k log n)。
这是您的维基百科 link 中提到的 "centered interval tree"。基于红黑树实现其中之一是合理的：
- 主树是红黑树。每个节点都有其中心点和间隔列表。每当插入不与任何现有中心点重叠的新间隔时，都会创建一个新节点。只要删除所有中心点重叠间隔，就会删除一个节点。
- 为平衡 RB 树而执行的旋转操作将要求您将一些中心点重叠间隔从子节点向上移动到它们的新父节点。每个节点都应该将其中心点重叠间隔列表存储在其他红黑树中，以便可以在 log(n) 时间内完成此移动。请注意，RB 树每 insert/delete.
执行摊销的恒定旋转次数
但是...因为您似乎没有已经用 RB 树完成了这个，而且 RB 树很复杂，我建议用 treaps 做同样的事情相反：https://en.wikipedia.org/wiki/Treap
Treaps 会比 RB 树容易得多，因为它们开始时更简单，而且它们不需要旋转来保持它们的平衡，这使得维护中心点重叠的列表变得容易得多间隔。这些间隔也可以存储在 treap 中。
容易多了...但还是没那么容易:-)
我有一组对象，它们存储由低值和高值给出的间隔。我正在寻找一种数据结构，这将使我能够实时获取所有对象，其间隔与给定点重叠。我还需要能够尽快添加和删除单个对象。 Interval trees基于红黑树的插入和删除时间为O(log n)，O(n)space。但是查找所有重叠的查询需要 O(k log n) 时间，如果有很多重叠间隔，这可能比暴力搜索更糟糕。有更好的方法吗？
间隔树是为这项工作制作的。找到与一个点重叠的所有间隔需要 O(k + log n) 时间，而不是 O(k log n)。
这是您的维基百科 link 中提到的 "centered interval tree"。基于红黑树实现其中之一是合理的：
- 主树是红黑树。每个节点都有其中心点和间隔列表。每当插入不与任何现有中心点重叠的新间隔时，都会创建一个新节点。只要删除所有中心点重叠间隔，就会删除一个节点。
- 为平衡 RB 树而执行的旋转操作将要求您将一些中心点重叠间隔从子节点向上移动到它们的新父节点。每个节点都应该将其中心点重叠间隔列表存储在其他红黑树中，以便可以在 log(n) 时间内完成此移动。请注意，RB 树每 insert/delete. 执行摊销的恒定旋转次数
但是...因为您似乎没有已经用 RB 树完成了这个，而且 RB 树很复杂，我建议用 treaps 做同样的事情相反：https://en.wikipedia.org/wiki/Treap
Treaps 会比 RB 树容易得多，因为它们开始时更简单，而且它们不需要旋转来保持它们的平衡，这使得维护中心点重叠的列表变得容易得多间隔。这些间隔也可以存储在 treap 中。
容易多了...但还是没那么容易:-)