Interval tree

In computer science, the interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval. An important special case is finding all intervals that contain a particular point.

An interval tree is a simple ordered tree, for example a binary search tree or self-balancing binary search tree, where the tree is ordered by the 'low' values of the intervals, and an extra annotation is added to every node recording the maximum high value of both its subtrees. It is simple to maintain this attribute in only O(h) steps during each addition or removal of a node, where h is the height of the node added or removed in the tree, by updating all ancestors of the node from the bottom up.

Now, it's known that two intervals A and B overlap only when both A.low ≤ B.high and A.high ≥ B.low. When searching the trees for nodes overlapping with a given interval, you can immediately skip:

• all nodes to the right of nodes whose low value is past the end of the given interval.
• all nodes that have their maximum 'high' value below the start of the given interval.

This is easily extended to higher dimensions, by cycling through the dimensions at each level of the tree. For example, for two dimensions, the odd levels of the tree might contain ranges for the x coordinate, while the even levels contain ranges for the y coordinate.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 14.3: Interval trees, pp.311–317.
• Mark de Berg, Marc van Krevald, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 10.1: Interval Trees, pp.212-217.