问题标签 [interval-tree]

我试图找到一个没有病毒或限制性许可的有效 C++ 区间树实现（很可能基于红黑树）。任何指向干净的轻量级独立实现的指针？对于我想到的用例，一开始就知道一组间隔（比如说一百万），我希望能够快速获得与给定间隔重叠的间隔列表。因此树一旦构建就不会改变——只需要快速查询。

假设我有一个区间（或范围）列表（例如 10-15、5-7、9-12 ..）。问题是找到重叠的范围子集。当然，我可以为此使用区间树。

我遇到的实际问题是有多个范围。最好用一个例子来解释：

1. 10-15、5-7、9-12
2. 1-2、3-6、14-15
3. 3-5、9-15、10-15

在上述情况下，（1）和（2）在第二范围内有重叠，在（3）和（1）、（2）之间在第三范围内有重叠。

基本上，我需要找到项目列表之间的所有重叠。

也许我可以使用 3 个单独的区间树来找出答案。有一个更好的方法吗？

我需要一个Java 中的IntervalTree或 RangeTree 实现，并且很难找到一个具有有效删除支持的实现。

sun.jvm.hotspot.utilities.IntervalTree有一个内置的，但是 RBTree 超类中的deleteNode方法指出：

尝试从树中删除节点最终会引发异常：

节点的最大端点未正确更新

delete在 sun.jvm.hotspot.utilities.IntervalTree 的子类中正确实现功能有多难？或者是否有另一个已经正确实现的间隔树实现？

目前我只是清除树并在每次删除时重新填充它，这远非理想（注意：在 RBTree 中设置 DEBUGGING=false 极大地加快了速度）。

我正在寻找一种类似于 CLR 中的红黑区间树的区间树算法，但默认情况下它支持合并区间，因此不会有任何重叠区间。

换句话说，如果您有一棵包含两个区间 [2,3] 和 [5,6] 的树，并且您添加了区间 [4,4]，那么结果将是一棵仅包含一个区间 [2,6] 的树。

谢谢

更新：我正在考虑的用例是计算传递闭包。区间集用于存储后继集，因为已发现它们非常紧凑。但是，如果您将区间集表示为链表，我发现在某些情况下它们可能会变得非常大，因此找到插入点所需的时间也是如此。因此我对区间树感兴趣。此外，可能会有很多将一棵树与另一棵树合并（即一组 OR 操作） - 如果两棵树都很大，那么使用两棵树的中序游走而不是重复插入每个间隔来创建一棵新树可能会更好。

这是一个有趣的问题：给定一组 N 个区间（[start, end]），使用区间树来找到重叠区间的最大数量。

StackOverflow 上的一个类似问题提供了一个 O(N) 解决方案，但如果我们可以将区间预处理为区间树，也许我们可以在对数时间内找到解决方案。

事实上，Cormen 等人在“算法简介”一书中的一个练习问题表明，这可以通过增加红黑区间树来实现。任何想法如何做到这一点？

我可以在这里找到一个 C++ 的，但没有纯 C 的。任何指针？

有人知道interval treeC++ 中有什么好的实现吗？

显然，模板驱动的东西，更好的类似boost风格。

还有一个问题 - 如果有人测试过，在实践中，std::vector基于基本的带排序的区间树实现是否可以击败通用区间树（使用 O(lg) 操作）？

最近几天我一直在寻找 R-Tree 的稳定实现，支持无限维度（20 左右就足够了）。我只找到了这个http://sourceforge.net/projects/jsi/但它们只支持二维。

另一个选项是区间树的多维实现。

也许我对使用 R-Tree 或 Intervall-Tree 来解决我的问题的想法完全错误，所以我简短地陈述问题，您可以将您的想法发送给我。

我需要解决的问题是某种最近邻搜索。我有一组天线和房间，每个天线都有一个整数间隔。例如天线 1，最小 -92，最大 -85。事实上，它可以表示为房间 -> 天线组 -> 天线间隔。这个想法是，每个房间在 R-Tree 中跨越天线维度上的一个盒子，并在每个维度上由间隔跨越。

如果我得到一个带有 N 天线和每个天线值的查询，那么我可以将信息表示为房间中的查询点，并检索到该点“最近”的房间。

希望您对问题和我的想法有所了解。

我正在寻找一个区间树 C# 集合类。

我需要能够添加间隔，最好是 2D，否则我可以组合两个标准的 1D 间隔树。

我还需要能够找出哪些间隔与给定间隔重叠。

我找到了这个intervaltree.codeplex.com但是

没有与此版本相关的下载。

编辑：

在此处继续：使用其他代码的 C#

我从这里下载了一个 C# 区间树集合类类http://intervaltree.codeplex.com/SourceControl/list/changesets -> 右手边 -> 下载。

但是我无法在我的 Microsoft Visual C# 2010 Express（也运行 C# XNA）上打开整个项目，因为

此版本的应用程序不支持解决方案文件夹

另外我只是希望该类在我自己的单独项目中单独使用。

我试图将三个重要的看似文件复制到我的项目Interval.cs中，但这会产生编译错误IntervalNode.csIntervalTree.cs

没有处理这种文件类型的进口商

我还尝试将这三个文件的内容复制并粘贴到我的项目中，将它们封装到自己的命名空间以及大量代码中。我不得不重新安排一些使用，但遇到了可能需要 PowerCollections .dll 和 .pcb 文件作为using Wintellect.PowerCollections;原因的问题

找不到类型或命名空间名称“Wintellect”（您是否缺少 using 指令或程序集引用？）

我不确定如何继续，或者我是否在做正确的事情来让这门课正常工作。