Editing Interval tree (section)

== Augmented tree ==
[[File:Example of augmented tree with low value as the key and maximum high as extra annotation.png|thumb|236px|An augmented tree with low value as the key and maximum high as the extra annotation.{{paragraph break}}For example, when testing if the given interval ''[40 ,60)'' overlaps the intervals in the tree shown above, we see that it does not overlap the interval ''[20, 36)'' in the root, but since the root's low value (20) is less than the sought high value (60), we must search the right subtree.  The left subtree's maximum high of 41 exceeds the sought low value (40), so we must search the left subtree as well.  However, both descendants of the ''[3, 41)'' node have maximum highs less than 40, so the left subtree search ends there and it is not necessary to search them.]]
Another way to represent intervals is described in {{harvtxt|Cormen|Leiserson|Rivest|Stein|2009|loc=Section 14.3: Interval trees, pp.&nbsp;348&ndash;354}}.

Both insertion and deletion require <math>O(\log n)</math> time, with <math>n</math> being the total number of intervals in the tree prior to the insertion or deletion operation.

An augmented tree can be built from a simple ordered tree, for example a [[binary search tree]] or [[self-balancing binary search tree]], ordered by the 'low' values of the intervals. An extra annotation is then added to every node, recording the maximum upper value among all the intervals from this node down. Maintaining this attribute involves updating all ancestors of the node from the bottom up whenever a node is added or deleted. This takes only O(''h'') steps per node addition or removal, where ''h'' is the height of the node added or removed in the tree. If there are any [[tree rotation]]s during insertion and deletion, the affected nodes may need updating as well.

Now, it is known that two intervals <math>A</math> and <math>B</math> overlap only when both <math>A_{\textrm{low}} \leq B_{\textrm{high}}</math> and <math>A_{\textrm{high}} \geq B_{\textrm{low}}</math>. When searching the trees for nodes overlapping with a given interval, you can immediately skip:
* all nodes to the right of nodes whose low value is past the end of the given interval.
* all nodes that have their maximum high value below the start of the given interval.

=== Membership queries ===
Some performance may be gained if the tree avoids unnecessary traversals. These can occur when adding intervals that already exist or removing intervals that don't exist.

A total order can be defined on the intervals by ordering them first by their lower bounds and then by their upper bounds. Then, a membership check can be performed in <math>O(\log n)</math> time, versus the <math>O(k + \log n)</math> time required to find duplicates if <math>k</math> intervals overlap the interval to be inserted or removed. This solution has the advantage of not requiring any additional structures. The change is strictly algorithmic. The disadvantage is that membership queries take <math>O(\log n)</math> time.

Alternately, at the rate of <math>O(n)</math> 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.

===Java example: Adding a new interval to the tree===

The key of each node is the interval itself, hence nodes are ordered first by low value and finally by high value, and the value of each node is the end point of the interval:

<syntaxhighlight lang="java">
public void add(Interval i) {
    put(i, i.getEnd());
}
</syntaxhighlight>

===Java example: Searching a point or an interval in the tree===

To search for an interval, one walks the tree, using the key (<code>n.getKey()</code>) and high value (<code>n.getValue()</code>) to omit any branches that cannot overlap the query. The simplest case is a point query:

<syntaxhighlight lang="java">
// Search for all intervals containing "p", starting with the
// node "n" and adding matching intervals to the list "result"
public void search(IntervalNode n, Point p, List<Interval> result) {
    // Don't search nodes that don't exist
    if (n == null)
        return;

    // If p is to the right of the rightmost point of any interval
    // in this node and all children, there won't be any matches.
    if (p.compareTo(n.getValue()) > 0)
        return;

    // Search left children
    search(n.getLeft(), p, result);

    // Check this node
    if (n.getKey().contains(p))
        result.add(n.getKey());

    // If p is to the left of the start of this interval,
    // then it can't be in any child to the right.
    if (p.compareTo(n.getKey().getStart()) < 0)
        return;

    // Otherwise, search right children
    search(n.getRight(), p, result);
}
</syntaxhighlight>
where
:<code>''a''.compareTo(''b'')</code> returns a negative value if a < b
:<code>''a''.compareTo(''b'')</code> returns zero if a = b
:<code>''a''.compareTo(''b'')</code> returns a positive value if a > b

The code to search for an interval is similar, except for the check in the middle:
<syntaxhighlight lang="java">
// Check this node
if (n.getKey().overlapsWith(i))
    result.add (n.getKey());
</syntaxhighlight>

<code>overlapsWith()</code> is defined as:
<syntaxhighlight lang="java">
public boolean overlapsWith(Interval other) {
    return start.compareTo(other.getEnd()) <= 0 &&
           end.compareTo(other.getStart()) >= 0;
}
</syntaxhighlight>

===Higher dimensions===
{{Unreferenced section|date=November 2022}}

Augmented trees can be extended to higher dimensions by cycling through the dimensions at each level of the tree. For example, for two dimensions, the odd levels of the tree might contain ranges for the ''x''-coordinate, while the even levels contain ranges for the ''y''-coordinate. 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.

A simpler solution is to use nested interval trees. First, create a tree using the ranges for the ''y''-coordinate. Now, for each node in the tree, add another interval tree on the ''x''-ranges, for all elements whose ''y''-range is the same as that node's ''y''-range.

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

At first, the additional cost of the nested trees might seem prohibitive, but this is usually not so. As with the non-nested solution earlier, one node is needed per ''x''-coordinate, yielding the same number of nodes for both solutions. The only additional overhead is that of the nested tree structures, one per vertical interval. This structure is usually of negligible size, consisting only of a pointer to the root node, and possibly the number of nodes and the depth of the tree.