Editing Interval tree (section)

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