Editing Interval tree (section)

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