Editing Interval tree (section)

== Centered interval tree ==

Queries require <math>O(\log n + m)</math> time, with <math>n</math> being the total number of intervals and <math>m</math> being the number of reported results. Construction requires <math>O(n \log n)</math> time, and storage requires <math>O(n)</math> space.

=== Construction ===

Given a set of <math>n</math> 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 <math>x_{\textrm{center}}</math> (in practice,   <math>x_{\textrm{center}}</math> should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of   <math>x_{\textrm{center}}</math> which we'll call <math>S_{\textrm{left}}</math>, those completely to the right of   <math>x_{\textrm{center}}</math> which we'll call  <math>S_{\textrm{right}}</math>, and those overlapping   <math>x_{\textrm{center}}</math> which we'll call  <math>S_{\textrm{center}}</math>.

The intervals in  <math>S_{\textrm{left}}</math> and  <math>S_{\textrm{right}}</math> are recursively divided in the same manner until there are no intervals left.

The intervals in <math>S_{\textrm{center}}</math> 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 <math>x</math>. 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, <math>x</math> is compared to  <math>x_{\textrm {center}}</math>, the midpoint used in node construction above.  If <math>x</math> is less than  <math>x_{\textrm {center}}</math>, the leftmost set of intervals,  <math>S_{\textrm{left}}</math>, is considered. If <math>x</math> is greater than  <math>x_{\textrm {center}}</math>, the rightmost set of intervals,  <math>S_{\textrm{right}}</math>, is considered.

[[File:Check if a point overlaps the intervals in S center of a centered interval tree.svg|thumb|280px|right|All intervals in  <math>S_{\textrm {center}}</math> that begin before <math>x</math> must overlap <math>x</math> if <math>x</math> is less than  <math>x_{\textrm {center}}</math>.<br />Similarly, the same technique also applies in checking a given interval. If a given interval ends at  ''y'' and ''y'' is less than  <math>x_{\textrm {center}}</math>, all intervals in  <math>S_{\textrm {center}}</math> that begin before ''y'' must also overlap the given interval.]]
As each node is processed as we traverse the tree from the root to a leaf, the ranges in its  <math>S_{\textrm {center}}</math> are processed. If <math>x</math> is less than  <math>x_{\textrm {center}}</math>, we know that all intervals in  <math>S_{\textrm {center}}</math> end after <math>x</math>, or they could not also overlap  <math>x_{\textrm {center}}</math>. Therefore, we need only find those intervals in  <math>S_{\textrm {center}}</math> that begin before <math>x</math>. We can consult the lists of  <math>S_{\textrm {center}}</math> that have already been constructed. Since we only care about the interval beginnings in this scenario, we can consult the list sorted by beginnings. Suppose we find the closest number no greater than <math>x</math> in this list. All ranges from the beginning of the list to that found point overlap <math>x</math> because they begin before <math>x</math> and end after <math>x</math> (as we know because they overlap  <math>x_{\textrm {center}}</math> which is larger than <math>x</math>). Thus, we can simply start enumerating intervals in the list until the startpoint value exceeds <math>x</math>.

Likewise, if <math>x</math> is greater than  <math>x_{\textrm {center}}</math>, we know that all intervals in  <math>S_{\textrm {center}}</math> must begin before <math>x</math>, so we find those intervals that end after <math>x</math> using the list sorted by interval endings.

If <math>x</math> exactly matches  <math>x_{\textrm {center}}</math>, all intervals in  <math>S_{\textrm {center}}</math> can be added to the results without further processing and tree traversal can be stopped.

==== With an interval ====

For a result interval <math>r</math> to intersect our query interval <math>q</math> one of the following must hold:

* either the start or end point of <math>r</math> is in <math>q</math>; or
*<math>r</math> completely encloses <math>q</math>.

{{Confusing|date=February 2020}}
We first find all intervals with start and/or end points inside <math>q</math> using a separately-constructed tree. In the one-dimensional case, we can use a search tree containing all the start and end points in the interval set, each with a pointer to its corresponding interval. A binary search in <math>O(\log n)</math> time for the start and end of <math>q</math> reveals the minimum and maximum points to consider. Each point within this range references an interval that overlaps <math>q</math> and is added to the result list. Care must be taken to avoid duplicates, since an interval might both begin and end within <math>q</math>. 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 <math>q</math>. To find these, we pick any point inside <math>q</math> 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 <math>N</math> with identical query and construction time and <math>O(n \log n)</math> space.

First, a [[range tree]] in <math>N</math> dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region <math>R</math>. 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,  <math>N</math> interval trees are created, and one axis intersecting <math>R</math> is queried for each. For example, in two dimensions, the bottom of the square  <math>R</math> (or any other horizontal line intersecting <math>R</math>) would be queried against the interval tree constructed for the horizontal axis. Likewise, the left (or any other vertical line intersecting <math>R</math>) 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, <math>x</math> is compared with  <math>S_{\textrm {center}}</math> 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  <math>S_{\textrm {center}}</math> that overlap region <math>R</math>.

=== 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).
[[File:binary search tree delete.svg|thumb|640px|center|Deleting a node with two children from a binary search tree using the in-order predecessor (rightmost node in the left subtree, labelled '''6''').]]
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.