Interval tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an interval tree is a <a href="/facts/Tree_(data_structure)/RcXz9noF">tree data structure</a> to hold <a href="/facts/Interval_(mathematics)/e9se3vTe">intervals</a>. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the <a href="/facts/Segment_tree/mPH7YB9s">segment tree</a>.
The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 time, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is <a href="/facts/Asymptotically_optimal/fnfvbMYE">asymptotically optimal</a>; however, we can do better by considering <a href="/facts/Output-sensitive_algorithm/5vAv585y">output-sensitive algorithms</a>, where the runtime is expressed in terms of 
 
 
 
 m
 
 
 {\displaystyle m}
 
, the number of intervals produced by the query. Interval trees have a query time of 
 
 
 
 O
 (
 log
 ⁡
 n
 +
 m
 )
 
 
 {\displaystyle O(\log n+m)}
 
 and an initial creation time of 
 
 
 
 O
 (
 n
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(n\log n)}
 
, while limiting memory consumption to 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
. After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 time. If the endpoints of intervals are within a small integer range (e.g., in the range 
 
 
 
 [
 1
 ,
 …
 ,
 O
 (
 n
 )
 ]
 
 
 {\displaystyle [1,\ldots ,O(n)]}
 
), faster and in fact optimal data structures exist with preprocessing time 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 and query time 
 
 
 
 O
 (
 1
 +
 m
 )
 
 
 {\displaystyle O(1+m)}
 
 for reporting 
 
 
 
 m
 
 
 {\displaystyle m}
 
 intervals containing a given query point (see for a very simple one).

Interval tree open-in-new

Interval tree