Interval tree

It is often used for windowing queries,[1] 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.

), faster and in fact optimal data structures exist[2][3] with preprocessing time

We start by taking the entire range of all the intervals and dividing it in half at

that overlap the center point are stored in a separate data structure linked to the node in the interval tree.

The result is a binary tree with each node storing: 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.

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.

As each node is processed as we traverse the tree from the root to a leaf, the ranges in its

Thus, we can simply start enumerating intervals in the list until the startpoint value exceeds

can be added to the results without further processing and tree traversal can be stopped.

one of the following must hold: We first find all intervals with start and/or end points inside

This can be done using a binary flag on each interval to mark whether or not it has been added to the result set.

and use the algorithm above to find all intervals intersecting that point (again, being careful to remove duplicates).

The interval tree data structure can be generalized to a higher dimension

dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region

Instead of two sorted lists of points as was used in the one-dimensional case, a range tree is constructed.

This is more complex than a normal binary tree deletion operation.

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 consequence, this may result in new empty nodes, which must be deleted, following the same algorithm again.

being the total number of intervals in the tree prior to the insertion or deletion operation.

If there are any tree rotations during insertion and deletion, the affected nodes may need updating as well.

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.

The simplest case is a point query: where The code to search for an interval is similar, except for the check in the middle: overlapsWith() is defined as: Augmented trees can be extended to higher dimensions by cycling through the dimensions at each level of the tree.

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.

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

The only additional overhead is that of the nested tree structures, one per vertical interval.

Also we store the minimum and maximum possible value of the subtree in each node (thus the symmetry).

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.