快速时间间隔查找的数据结构 [英] 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屋！