时间戳

首页 > 解决方案 > 寻找有效的区间树算法

algorithm - 寻找有效的区间树算法

问题描述

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

标签： algorithmtreecomplexity-theoryintervals

解决方案

间隔树是为这项工作制作的。找到与一个点重叠的所有间隔需要 O(k + log n) 时间，而不是 O(k log n)。

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

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

但是......因为您似乎还没有使用 RB-trees 完成此操作，并且 RB-trees 很复杂，所以我建议您使用 treaps 做同样的事情：https ://en.wikipedia.org/wiki/Treap

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

容易得多......但仍然不是那么容易:-)

推荐阅读