Editing Interval tree (section)

==Medial- or length-oriented tree==
{{Unreferenced section|date=October 2016}}
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 <math>\left( a_{i}, b_i \right)</math>, for <math>i=0,1</math>, the overlap test can be performed as follows:

<math>a_0 < b_1</math> and <math>a_1 < b_0</math>

This can be simplified using the sum and difference:

<math>s_i = a_i + b_i</math>

<math>d_i = b_i - a_i</math>

Which reduces the overlap test to:

<math>\left| s_1 - s_0 \right| < d_0 + d_1</math>

===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 <math>d_i</math> 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 <math>a_q, b_q, m_q, d_q</math> for the query interval, and <math>M_n</math> for the key of a node (compared to <math>m_i</math> 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 <math>\min \left\{ d_i \right\}</math> for intervals inside this node (not its children) to overlap with query interval (knowing <math>m_i = M_n</math>):

<math>\min \left\{ d_i \right\} = \left| m_q - M_n \right| - d_q</math>

and perform a query on its binary heap for the <math>d_i</math>'s bigger than <math>\min \left\{ d_i \right\}</math>

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.