In computer science, an interval tree is a tree data structure to hold intervals. 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 segment tree.
The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires time, where 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 asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of , the number of intervals produced by the query. Interval trees have a query time of and an initial creation time of , while limiting memory consumption to . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in time. If the endpoints of intervals are within a small integer range (e.g., in the range ), faster and in fact optimal data structures exist with preprocessing time and query time for reporting intervals containing a given query point (see for a very simple one).
Naive approach
In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naive approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in time, but the results must be merged, requiring time. This gives us queries in , which is no better than brute-force.
Interval trees solve this problem. This article describes two alternative designs for an interval tree, dubbed the centered interval tree and the augmented tree.
Centered interval tree
Queries require time, with being the total number of intervals and being the number of reported results. Construction requires time, and storage requires space.
Construction
Given a set of intervals on the number line, we want to construct a data structure so that we can efficiently retrieve all intervals overlapping another interval or point.
We start by taking the entire range of all the intervals and dividing it in half at (in practice, should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of which we'll call , those completely to the right of which we'll call , and those overlapping which we'll call .
The intervals in and are recursively divided in the same manner until there are no intervals left.
The intervals in that overlap the center point are stored in a separate data structure linked to the node in the interval tree. This data structure consists of two lists, one containing all the intervals sorted by their beginning points, and another containing all the intervals sorted by their ending points.
The result is a binary tree with each node storing: A center point A pointer to another node containing all intervals completely to the left of the center point A pointer to another node containing all intervals completely to the right of the center point All intervals overlapping the center point sorted by their beginning point All intervals overlapping the center point sorted by their ending point
Intersecting
Given the data structure constructed above, we receive queries consisting of ranges or points, and return all the ranges in the original set overlapping this input.
With a point
The task is to find all intervals in the tree that overlap a given point . The tree is walked with a similar recursive algorithm as would be used to traverse a traditional binary tree, but with extra logic to support searching the intervals overlapping the "center" point at each node.
For each tree node, is compared to , the midpoint used in node construction above. If is less than , the leftmost set of intervals, , is considered. If is greater than , the rightmost set of intervals, , is considered.