用于快速时间间隔查找的数据结构

我有一组时间间隔In =（an，bn）。我需要运行大量看看UPS在那里我得到的时间吨和需要迅速返回包含吨，例如间隔，这些间隔，使得的< = T < = BN。用于快速时间间隔查找的数据结构

什么是一个很好的数据结构或者算法？

如果重要，在我的情况下，和和bn是整数。

2009-10-16 David Norman

内存限制？ – ChaosPandion 2009-10-16 20:22:39

没有内存限制 – 2009-10-16 20:23:14

Java解决方案：https://stackoverflow.com/questions/13399821/data-structures-that-can-map-a-range-of-keys-to-a-value – Vadzim 2017-05-24 11:18:44

您要找的是一个Interval Tree（这是一种Range Tree）。

这些对象查找时间与其他树结构（例如RB树）相似，所以您应该看到使用类似Java TreeMap或STL映射的类似性能。

Code for Red-black trees and interval trees从MIT
有一个在CGAL Library一个C++ implementation。
这里有一个C# Implementation

来源

2009-10-16 21:09:00 tgamblin

有一个C++实现http://www.mit.edu/~emin/source_code/cpp_trees/index处的间隔树。HTML，链接从http://stackoverflow.com/questions/212808/help-finding-c-interval-tree-algorithm-implementation – 2009-10-16 21:14:54

不错。感谢您的链接！ – tgamblin 2009-10-16 21:18:50

[C＃实现]（http://www.emilstefanov.net/Projects/RangeSearchTree.aspx）的链接不再有效。 – krlzlx 2017-02-22 13:30:40

这基本上是一个空间分割问题。你有一个很大的容器空间和一个特定的空间，它触及什么容器？很多游戏必须解决这个问题，所以从这里开始并不是一个坏主意。寻找关于“广泛相位碰撞检测”的文章。

要做到这一点最简单的方法是你的电话号码空间分成固定件数。每件作品都知道哪些作品集与作品相交，哪些是你在添加新作品集时计算出来的。现在，当你有一个点时，不是只测试每一个集合，你只需要检查该点中包含的集合。

另一个通用和高效的算法是二进制空间分区。该算法将您的空间分为两部分。每一方都会知道哪些组合与它相交。你可以递归地重复这个过程到你想要的精度（尽管创建一个小于最小集的范围的细分是没有意义的）。

来源

2009-10-16 20:32:08 Kai

你的问题只是一维的，所以它比在大多数游戏中的空间分割问题简单一些。你可能只是一个简单的BST，并且在每一片叶子中记住叶子左边的区间列表。如果你有间隔A（0,10）和B（5,15），那么树的叶子将是（0与空列表），（5与A），（10与A，B）和（15与B）。

来源

2009-10-16 21:02:31 cube

欢迎您来看看它究竟解决这一问题的C# implementation I've posted on CodePlex for IntervalTree。

伊多。

来源

2011-09-28 06:07:45

用于快速时间间隔查找的数据结构

回答

相关问题