Interval tree

Centered interval tree

Queries require ${\displaystyle O(\log n+m)}$ time, with ${\displaystyle n}$ being the total number of intervals and ${\displaystyle m}$ being the number of reported results. Construction requires ${\displaystyle O(n\log n)}$ time, and storage requires ${\displaystyle O(n)}$ space.

Construction

Given a set of ${\displaystyle n}$ intervals on the number line, a data structure needs to be constructed so that all intervals overlapping another interval or point can be efficiently retrieved.

First, the entire range of all the intervals is taken and divided in half at ${\displaystyle x_{\text{center}}}$ (in practice, ${\displaystyle x_{\text{center}}}$ should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of ${\displaystyle x_{\text{center}}}$, called ${\displaystyle S_{\text{left}}}$, those completely to the right of ${\displaystyle x_{\text{center}}}$, called ${\displaystyle S_{\text{right}}}$, and those overlapping ${\displaystyle x_{\text{center}}}$, called ${\displaystyle S_{\text{center}}}$.

The intervals in ${\displaystyle S_{\text{left}}}$ and ${\displaystyle S_{\text{right}}}$ are recursively divided in the same manner until there are no intervals left.

The intervals in ${\displaystyle S_{\text{center}}}$ 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

Interval trees allow for quickly computing all the ranges overlapping any input.

With a point

The task is to find all intervals in the tree that overlap a given point ${\displaystyle x}$. 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, ${\displaystyle x}$ is compared to ${\displaystyle x_{\text{center}}}$, the midpoint used in node construction above. If ${\displaystyle x}$ is less than ${\displaystyle x_{\text{center}}}$, the leftmost set of intervals, ${\displaystyle S_{\text{left}}}$, is considered. If ${\displaystyle x}$ is greater than ${\displaystyle x_{\text{center}}}$, the rightmost set of intervals, ${\displaystyle S_{\text{right}}}$, is considered.

As each node is processed as the tree is traversed from the root to a leaf, the ranges in its ${\displaystyle S_{\text{center}}}$ are processed. If ${\displaystyle x}$ is less than ${\displaystyle x_{\text{center}}}$, all intervals in ${\displaystyle S_{\text{center}}}$ must end after ${\displaystyle x}$, or they could not also overlap ${\displaystyle x_{\text{center}}}$. Therefore, it is only necessary find those intervals in ${\displaystyle S_{\text{center}}}$ that begin before ${\displaystyle x}$. The lists of ${\displaystyle S_{\text{center}}}$, which have already been constructed, can be consulted. Since only the interval beginnings are relevant in this scenario, the list can be sorted by beginnings. If the closest number no greater than ${\displaystyle x}$ is found in this list, all ranges from the beginning of the list to that found point overlap ${\displaystyle x}$ because they begin before ${\displaystyle x}$ and end after ${\displaystyle x}$ (because they overlap ${\displaystyle x_{\text{center}}}$ which is larger than ${\displaystyle x}$). Thus, the intervals in the list can be enumerated until the startpoint value exceeds ${\displaystyle x}$.

Likewise, if ${\displaystyle x}$ is greater than ${\displaystyle x_{\text{center}}}$, all intervals in ${\displaystyle S_{\text{center}}}$ must begin before ${\displaystyle x}$, so the intervals that end after ${\displaystyle x}$ can be found using the list sorted by interval endings.

If ${\displaystyle x}$ exactly matches ${\displaystyle x_{\text{center}}}$, all intervals in ${\displaystyle S_{\text{center}}}$ can be added to the results without further processing and tree traversal can be stopped.

With an interval

For a result interval ${\displaystyle r}$ to intersect the query interval ${\displaystyle q}$ one of the following must hold:

• either the start or end point of ${\displaystyle r}$ is in ${\displaystyle q}$; or
• ${\displaystyle r}$ completely encloses ${\displaystyle q}$.

We first find all intervals with start and/or end points inside ${\displaystyle q}$ using a separately-constructed tree. In the one-dimensional case, we construct a single search tree with all the start and end points in the interval set, each with a pointer to its corresponding interval. We then do a binary search for the start point of ${\displaystyle q}$ in ${\displaystyle O(\log n)}$ time, and traverse the tree in-order until we find the end point of ${\displaystyle q}$. Each interval we encounter is an interval which either starts or ends inside ${\displaystyle q}$ and thus overlaps ${\displaystyle q}$. These are all added to the result list. Care must be taken to avoid duplicates, since if an interval is completely enclosed by ${\displaystyle q}$ its start and end point will both encountered during the traversal. This can be done using a binary flag on each interval to mark whether or not it has been added to the result set.

Finally, we must find intervals that enclose ${\displaystyle q}$. To find these, we pick any point inside ${\displaystyle q}$ and use the algorithm above to find all intervals intersecting that point (again, being careful to remove duplicates).

Higher dimensions

The interval tree data structure can be generalized to a higher dimension ${\displaystyle N}$ with identical query and construction time and ${\displaystyle O(n\log n)}$ space.

First, a range tree in ${\displaystyle N}$ dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region ${\displaystyle R}$. Once the corresponding ranges are found, the only thing that is left are those ranges that enclose the region in some dimension. To find these overlaps, ${\displaystyle N}$ interval trees are created, and one axis intersecting ${\displaystyle R}$ is queried for each. For example, in two dimensions, the bottom of the square ${\displaystyle R}$ (or any other horizontal line intersecting ${\displaystyle R}$) would be queried against the interval tree constructed for the horizontal axis. Likewise, the left (or any other vertical line intersecting ${\displaystyle R}$) would be queried against the interval tree constructed on the vertical axis.

Each interval tree also needs an addition for higher dimensions. At each node we traverse in the tree, ${\displaystyle x}$ is compared with ${\displaystyle S_{\text{center}}}$ to find overlaps. Instead of two sorted lists of points as was used in the one-dimensional case, a range tree is constructed. This allows efficient retrieval of all points in ${\displaystyle S_{\text{center}}}$ that overlap region ${\displaystyle R}$.

Deletion

If after deleting an interval from the tree, the node containing that interval contains no more intervals, that node may be deleted from the tree. This is more complex than a normal binary tree deletion operation.

An interval may overlap the center point of several nodes in the tree. Since each node stores the intervals that overlap it, with all intervals completely to the left of its center point in the left subtree, similarly for the right subtree, it follows that each interval is stored in the node closest to the root from the set of nodes whose center point it overlaps.

Normal deletion operations in a binary tree (for the case where the node being deleted has two children) involve promoting a node further from the leaf to the position of the node being deleted (usually the leftmost child of the right subtree, or the rightmost child of the left subtree).

As a result of this promotion, some nodes that were above the promoted node will become its descendants; it is necessary to search these nodes for intervals that also overlap the promoted node, and move those intervals into the promoted node. As a consequence, this may result in new empty nodes, which must be deleted, following the same algorithm again.

Balancing

The same issues that affect deletion also affect rotation operations; rotation must preserve the invariant that nodes are stored as close to the root as possible.

Augmented tree

Another way to represent intervals is described in Cormen et al. (2009, Section 14.3: Interval trees, pp. 348–354).

Both insertion and deletion require ${\displaystyle O(\log n)}$ time, with ${\displaystyle n}$ being the total number of intervals in the tree prior to the insertion or deletion operation.

An augmented tree can be built from a simple ordered tree, for example a binary search tree or self-balancing binary search tree, ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(h) steps per node addition or removal, where h is the height of the node added or removed in the tree. If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well.

Now, it is known that two intervals ${\displaystyle A}$ and ${\displaystyle B}$ overlap only when both ${\displaystyle A_{\text{low}}\le B_{\text{high}}}$ and ${\displaystyle A_{\text{high}}\ge B_{\text{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.

Membership queries

Some performance may be gained if the tree avoids unnecessary traversals. These can occur when adding intervals that already exist or removing intervals that don't exist.

A total order can be defined on the intervals by ordering them first by their lower bounds and then by their upper bounds. Then, a membership check can be performed in ${\displaystyle O(\log n)}$ time, versus the ${\displaystyle O(k+\log n)}$ time required to find duplicates if ${\displaystyle k}$ intervals overlap the interval to be inserted or removed. This solution has the advantage of not requiring any additional structures. The change is strictly algorithmic. The disadvantage is that membership queries take ${\displaystyle O(\log n)}$ time.

Alternately, at the rate of ${\displaystyle O(n)}$ memory, membership queries in expected constant time can be implemented with a hash table, updated in lockstep with the interval tree. This may not necessarily double the total memory requirement, if the intervals are stored by reference rather than by value.

Java example: Adding a new interval to the tree

The key of each node is the interval itself, hence nodes are ordered first by low value and finally by high value, and the value of each node is the end point of the interval:

<span id="mw7A"></span><span class="kd" id="mw7Q">public</span><span class="w" id="mw7g"> </span><span class="kt" id="mw7w">void</span><span class="w" id="mw8A"> </span><span class="nf" id="mw8Q">add</span><span class="p" id="mw8g">(</span><span class="n" id="mw8w">Interval</span><span class="w" id="mw9A"> </span><span class="n" id="mw9Q">i</span><span class="p" id="mw9g">)</span><span class="w" id="mw9w"> </span><span class="p" id="mw-A">{</span> <span class="w" id="mw-Q"> </span><span class="n" id="mw-g">put</span><span class="p" id="mw-w">(</span><span class="n" id="mw_A">i</span><span class="p" id="mw_Q">,</span><span class="w" id="mw_g"> </span><span class="n" id="mw_w">i</span><span class="p" id="mwAQA">.</span><span class="na" id="mwAQE">getEnd</span><span class="p" id="mwAQI">());</span> <span class="p" id="mwAQM">}</span>

Java example: Searching a point or an interval in the tree

To search for an interval, one walks the tree, using the key (n.getKey()) and high value (n.getValue()) to omit any branches that cannot overlap the query. The simplest case is a point query:

<span id="mwAQo"></span><span class="c1" id="mwAQs">// Search for all intervals containing "p", starting with the</span> <span class="c1" id="mwAQw">// node "n" and adding matching intervals to the list "result"</span> <span class="kd" id="mwAQ0">public</span><span class="w" id="mwAQ4"> </span><span class="kt" id="mwAQ8">void</span><span class="w" id="mwARA"> </span><span class="nf" id="mwARE">search</span><span class="p" id="mwARI">(</span><span class="n" id="mwARM">IntervalNode</span><span class="w" id="mwARQ"> </span><span class="n" id="mwARU">n</span><span class="p" id="mwARY">,</span><span class="w" id="mwARc"> </span><span class="n" id="mwARg">Point</span><span class="w" id="mwARk"> </span><span class="n" id="mwARo">p</span><span class="p" id="mwARs">,</span><span class="w" id="mwARw"> </span><span class="n" id="mwAR0">List</span><span class="o" id="mwAR4"><</span><span class="n" id="mwAR8">Interval</span><span class="o" id="mwASA">></span><span class="w" id="mwASE"> </span><span class="n" id="mwASI">result</span><span class="p" id="mwASM">)</span><span class="w" id="mwASQ"> </span><span class="p" id="mwASU">{</span> <span class="w" id="mwASY"> </span><span class="c1" id="mwASc">// Don't search nodes that don't exist</span> <span class="w" id="mwASg"> </span><span class="k" id="mwASk">if</span><span class="w" id="mwASo"> </span><span class="p" id="mwASs">(</span><span class="n" id="mwASw">n</span><span class="w" id="mwAS0"> </span><span class="o" id="mwAS4">==</span><span class="w" id="mwAS8"> </span><span class="kc" id="mwATA">null</span><span class="p" id="mwATE">)</span> <span class="w" id="mwATI"> </span><span class="k" id="mwATM">return</span><span class="p" id="mwATQ">;</span> <span class="w" id="mwATU"> </span><span class="c1" id="mwATY">// If p is to the right of the rightmost point of any interval</span> <span class="w" id="mwATc"> </span><span class="c1" id="mwATg">// in this node and all children, there won't be any matches.</span> <span class="w" id="mwATk"> </span><span class="k" id="mwATo">if</span><span class="w" id="mwATs"> </span><span class="p" id="mwATw">(</span><span class="n" id="mwAT0">p</span><span class="p" id="mwAT4">.</span><span class="na" id="mwAT8">compareTo</span><span class="p" id="mwAUA">(</span><span class="n" id="mwAUE">n</span><span class="p" id="mwAUI">.</span><span class="na" id="mwAUM">getValue</span><span class="p" id="mwAUQ">())</span><span class="w" id="mwAUU"> </span><span class="o" id="mwAUY">></span><span class="w" id="mwAUc"> </span><span class="mi" id="mwAUg">0</span><span class="p" id="mwAUk">)</span> <span class="w" id="mwAUo"> </span><span class="k" id="mwAUs">return</span><span class="p" id="mwAUw">;</span> <span class="w" id="mwAU0"> </span><span class="c1" id="mwAU4">// Search left children</span> <span class="w" id="mwAU8"> </span><span class="n" id="mwAVA">search</span><span class="p" id="mwAVE">(</span><span class="n" id="mwAVI">n</span><span class="p" id="mwAVM">.</span><span class="na" id="mwAVQ">getLeft</span><span class="p" id="mwAVU">(),</span><span class="w" id="mwAVY"> </span><span class="n" id="mwAVc">p</span><span class="p" id="mwAVg">,</span><span class="w" id="mwAVk"> </span><span class="n" id="mwAVo">result</span><span class="p" id="mwAVs">);</span> <span class="w" id="mwAVw"> </span><span class="c1" id="mwAV0">// Check this node</span> <span class="w" id="mwAV4"> </span><span class="k" id="mwAV8">if</span><span class="w" id="mwAWA"> </span><span class="p" id="mwAWE">(</span><span class="n" id="mwAWI">n</span><span class="p" id="mwAWM">.</span><span class="na" id="mwAWQ">getKey</span><span class="p" id="mwAWU">().</span><span class="na" id="mwAWY">contains</span><span class="p" id="mwAWc">(</span><span class="n" id="mwAWg">p</span><span class="p" id="mwAWk">))</span> <span class="w" id="mwAWo"> </span><span class="n" id="mwAWs">result</span><span class="p" id="mwAWw">.</span><span class="na" id="mwAW0">add</span><span class="p" id="mwAW4">(</span><span class="n" id="mwAW8">n</span><span class="p" id="mwAXA">.</span><span class="na" id="mwAXE">getKey</span><span class="p" id="mwAXI">());</span> <span class="w" id="mwAXM"> </span><span class="c1" id="mwAXQ">// If p is to the left of the start of this interval,</span> <span class="w" id="mwAXU"> </span><span class="c1" id="mwAXY">// then it can't be in any child to the right.</span> <span class="w" id="mwAXc"> </span><span class="k" id="mwAXg">if</span><span class="w" id="mwAXk"> </span><span class="p" id="mwAXo">(</span><span class="n" id="mwAXs">p</span><span class="p" id="mwAXw">.</span><span class="na" id="mwAX0">compareTo</span><span class="p" id="mwAX4">(</span><span class="n" id="mwAX8">n</span><span class="p" id="mwAYA">.</span><span class="na" id="mwAYE">getKey</span><span class="p" id="mwAYI">().</span><span class="na" id="mwAYM">getStart</span><span class="p" id="mwAYQ">())</span><span class="w" id="mwAYU"> </span><span class="o" id="mwAYY"><</span><span class="w" id="mwAYc"> </span><span class="mi" id="mwAYg">0</span><span class="p" id="mwAYk">)</span> <span class="w" id="mwAYo"> </span><span class="k" id="mwAYs">return</span><span class="p" id="mwAYw">;</span> <span class="w" id="mwAY0"> </span><span class="c1" id="mwAY4">// Otherwise, search right children</span> <span class="w" id="mwAY8"> </span><span class="n" id="mwAZA">search</span><span class="p" id="mwAZE">(</span><span class="n" id="mwAZI">n</span><span class="p" id="mwAZM">.</span><span class="na" id="mwAZQ">getRight</span><span class="p" id="mwAZU">(),</span><span class="w" id="mwAZY"> </span><span class="n" id="mwAZc">p</span><span class="p" id="mwAZg">,</span><span class="w" id="mwAZk"> </span><span class="n" id="mwAZo">result</span><span class="p" id="mwAZs">);</span> <span class="p" id="mwAZw">}</span>

where

a.compareTo(b) returns a negative value if a < b

a.compareTo(b) returns zero if a = b

a.compareTo(b) returns a positive value if a > b

The code to search for an interval is similar, except for the check in the middle:

<span id="mwAa4"></span><span class="c1" id="mwAa8">// Check this node</span> <span class="k" id="mwAbA">if</span><span class="w" id="mwAbE"> </span><span class="p" id="mwAbI">(</span><span class="n" id="mwAbM">n</span><span class="p" id="mwAbQ">.</span><span class="na" id="mwAbU">getKey</span><span class="p" id="mwAbY">().</span><span class="na" id="mwAbc">overlapsWith</span><span class="p" id="mwAbg">(</span><span class="n" id="mwAbk">i</span><span class="p" id="mwAbo">))</span> <span class="w" id="mwAbs"> </span><span class="n" id="mwAbw">result</span><span class="p" id="mwAb0">.</span><span class="na" id="mwAb4">add</span><span class="w" id="mwAb8"> </span><span class="p" id="mwAcA">(</span><span class="n" id="mwAcE">n</span><span class="p" id="mwAcI">.</span><span class="na" id="mwAcM">getKey</span><span class="p" id="mwAcQ">());</span>

overlapsWith() is defined as:

<span id="mwAck"></span><span class="kd" id="mwAco">public</span><span class="w" id="mwAcs"> </span><span class="kt" id="mwAcw">boolean</span><span class="w" id="mwAc0"> </span><span class="nf" id="mwAc4">overlapsWith</span><span class="p" id="mwAc8">(</span><span class="n" id="mwAdA">Interval</span><span class="w" id="mwAdE"> </span><span class="n" id="mwAdI">other</span><span class="p" id="mwAdM">)</span><span class="w" id="mwAdQ"> </span><span class="p" id="mwAdU">{</span> <span class="w" id="mwAdY"> </span><span class="k" id="mwAdc">return</span><span class="w" id="mwAdg"> </span><span class="n" id="mwAdk">start</span><span class="p" id="mwAdo">.</span><span class="na" id="mwAds">compareTo</span><span class="p" id="mwAdw">(</span><span class="n" id="mwAd0">other</span><span class="p" id="mwAd4">.</span><span class="na" id="mwAd8">getEnd</span><span class="p" id="mwAeA">())</span><span class="w" id="mwAeE"> </span><span class="o" id="mwAeI"><=</span><span class="w" id="mwAeM"> </span><span class="mi" id="mwAeQ">0</span><span class="w" id="mwAeU"> </span><span class="o" id="mwAeY">&&</span> <span class="w" id="mwAec"> </span><span class="n" id="mwAeg">end</span><span class="p" id="mwAek">.</span><span class="na" id="mwAeo">compareTo</span><span class="p" id="mwAes">(</span><span class="n" id="mwAew">other</span><span class="p" id="mwAe0">.</span><span class="na" id="mwAe4">getStart</span><span class="p" id="mwAe8">())</span><span class="w" id="mwAfA"> </span><span class="o" id="mwAfE">>=</span><span class="w" id="mwAfI"> </span><span class="mi" id="mwAfM">0</span><span class="p" id="mwAfQ">;</span> <span class="p" id="mwAfU">}</span>

Higher dimensions

Augmented trees can be 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. This approach effectively converts the data structure from an augmented binary tree to an augmented kd-tree, thus significantly complicating the balancing algorithms for insertions and deletions.

A simpler solution is to use nested interval trees. First, create a tree using the ranges for the y-coordinate. Now, for each node in the tree, add another interval tree on the x-ranges, for all elements whose y-range is the same as that node's y-range.

The advantage of this solution is that it can be extended to an arbitrary number of dimensions using the same code base.

At first, the additional cost of the nested trees might seem prohibitive, but this is usually not so. As with the non-nested solution earlier, one node is needed per x-coordinate, yielding the same number of nodes for both solutions. The only additional overhead is that of the nested tree structures, one per vertical interval. This structure is usually of negligible size, consisting only of a pointer to the root node, and possibly the number of nodes and the depth of the tree.

Medial- or length-oriented tree

A medial- or length-oriented tree is similar to an augmented tree, but symmetrical, with the binary search tree ordered by the medial points of the intervals. There is a maximum-oriented binary heap in every node, ordered by the length of the interval (or half of the length). Also we store the minimum and maximum possible value of the subtree in each node (thus the symmetry).

Overlap test

Using only start and end values of two intervals ${\displaystyle \left(a_i,b_i\right)}$, for ${\displaystyle i=0,1}$, the overlap test can be performed as follows:

${\displaystyle a_0<b_1}$ and ${\displaystyle a_1<b_0}$

This can be simplified using the sum and difference:

${\displaystyle s_i=a_i+b_i}$

${\displaystyle d_i=b_i-a_i}$

Which reduces the overlap test to:

${\displaystyle \left|s_1-s_0\right|<d_0+d_1}$

Adding interval

Adding new intervals to the tree is the same as for a binary search tree using the medial value as the key. We push ${\displaystyle d_i}$ onto the binary heap associated with the node, and update the minimum and maximum possible values associated with all higher nodes.

Searching for all overlapping intervals

Let's use ${\displaystyle a_q,b_q,m_q,d_q}$ for the query interval, and ${\displaystyle M_n}$ for the key of a node (compared to ${\displaystyle m_i}$ of intervals)

Starting with root node, in each node, first we check if it is possible that our query interval overlaps with the node subtree using minimum and maximum values of node (if it is not, we don't continue for this node).

Then we calculate ${\displaystyle min\left\{d_i\right\}}$ for intervals inside this node (not its children) to overlap with query interval (knowing ${\displaystyle m_i=M_n}$):

${\displaystyle min\left\{d_i\right\}=\left|m_q-M_n\right|-d_q}$

and perform a query on its binary heap for the ${\displaystyle d_i}$'s bigger than ${\displaystyle min\left\{d_i\right\}}$

Then we pass through both left and right children of the node, doing the same thing.

In the worst-case, we have to scan all nodes of the binary search tree, but since binary heap query is optimum, this is acceptable (a 2- dimensional problem can not be optimum in both dimensions)

This algorithm is expected to be faster than a traditional interval tree (augmented tree) for search operations. Adding elements is a little slower in practice, though the order of growth is the same.