Editing Interval tree (section)

==== 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.