快速时间间隔查找的数据结构 [英] Data structure for quick time interval look up
问题描述
我有一组时间间隔 In =(an,bn)。我需要运行很多查找,我被给予时间 t ,并且需要快速返回包含的间隔,例如这些间隔,使得一个<= t <= bn 。
这是一个很好的数据结构或算法?
如果重要,在我的情况下, 和 bn 是整数。
这些与其他树结构(例如RB树)具有对数查找时间,因此您应该看到使用类似Java TreeMap或STL映射的可比性能。 / p>
- 来自麻省理工学院的红黑树和间隔树的代码
- 有一个 C ++实现 doc_html / cgal_manual / contents.htmlrel =nofollow noreferrer> CGAL Library 。
- 这是一个 C#实现
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?
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).
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.
- 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屋!