Interval Tree - Augmented Tree

Augmented Tree

Another way to represent intervals is described in Cormen et al. (2001, Section 14.3: Interval trees, pp. 311–317).

Both insertion and deletion require O(log n) time, with n being the total number of intervals.

Use 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. Additionally, the tree rotations used during insertion and deletion may require updating the high value of the affected nodes.

Now, it is 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.

A total order can be defined on the intervals by ordering them first by their 'low' value and finally by their 'high' value. This ordering can be used to prevent duplicate intervals from being inserted into the tree in O(log n) time, versus the O(k + log n) time required to find duplicates if k intervals overlap a new interval.