用于快速时间间隔查找的数据结构 [英] Data structure for quick time interval look up
问题描述
我有一组时间间隔In = (an, bn).我需要在给定时间 t 的地方运行大量查找，并且需要快速返回包含 t 的间隔，例如，那些间隔 a <= t <= bn.
I have a set of time intervals In = (an, bn). I need to run lots of look ups where I'm given a time t and need to quickly return the intervals that contain t, e.g., those intervals such that an <= t <= bn.
对此有什么好的数据结构或算法?
What is a good data structure or algorithm for this?
如果重要的话，在我的例子中 an 和 bn 是整数.
If it matters, in my case the an and bn are integers.
推荐答案
What you are looking for is an Interval Tree (which is a type of Range Tree).
这些与其他树结构(例如，RB 树)一样具有对数查找时间，因此您应该会看到与使用 Java TreeMap 或 STL 映射等类似的性能.
These have logarithmic lookup time like other tree structures (e.g., RB trees), so you should see comparable performance to using something like a Java TreeMap or an STL map.
- 红黑树和区间树的代码 来自麻省理工学院
- C++ 实现在CGAL 图书馆.
- 这是一个 C# 实现
- Code for Red-black trees and interval trees from MIT
- There is a C++ implementation in the CGAL Library.
- Here's a C# Implementation
这篇关于用于快速时间间隔查找的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
