Interval search tree

Question

An interval is a data structure that represents a range (start & end, from & to, or min & max, etc.). An Interval Tree stores these intervals in a sorted tree structure that makes searching for range intersections much faster. Interval trees help answer questions like: "find all stored intervals that at least partially overlap with the range a to b"

Typical interval trees store the intervals using the start of the range as the key to a binary search tree.

This code implements the interval tree and has two methods:

• add(start, end) - inserts an interval to the tree
• overlap(start, end) - identifies if any interval in the tree overlaps with the input values.

The implemented algorithm follows an Augmented Interval Tree approach where each node maintains the maximum value contained in any of its child nodes. This maximum value is kept in sync by the add(start,end) method. Other details of the algorithm are:

• intervals are added to a binary tree with the start of interval as index to sort on.

• when intervals are added the maximum values of all parent nodes are updated to ensure they are in sync.

• to check for overlap it performs a descending scan of the tree using iteration, not recursion. It checks each node it descends to, and if the node:

  1. intersects the input arguments, it returns true.
  2. if (leftsubtree != null && leftsubtree.max > low) search left
  3. else search right

• Note, ranges only overlap if the ranges do more than just touch. The range [10,20] does not overlap with the range [20,30].

Despite of a brief stint in explaining my problem, more details can be obtained on this link here.

I'm looking for code review, best practices, optimizations etc. Also verifying complexity to be O(log(n)) to add and O(log(n)) to look for overlap. Do correct me if wrong.

public class IntervalSearchTree {

    private IntervalNode root;

    private class IntervalNode {
        IntervalNode left; 
        int start;
        int end;
        int maxEnd;
        IntervalNode right;

        public IntervalNode(IntervalNode left, int start, int end, int maxEnd, IntervalNode right) {
            this.left = left;
            this.start = start;
            this.end = end;
            this.maxEnd = maxEnd;
            this.right = right;
        }
    }

    /**
     * Adds an interval to the the calendar
     * 
     * @param start the start of interval
     * @param end   the end of the interval.
     */
    public void add (int start, int end) {
        if (start >= end) throw new IllegalArgumentException("The end " + end + " should be greater than start " + start);

        IntervalNode inode = root;
        while (inode != null) {
            inode.maxEnd = (end > inode.maxEnd) ? end : inode.maxEnd;
            if (start < inode.start) {
                if (inode.left == null) {
                    inode.left = new IntervalNode(null, start, end, end, null);
                    return;
                }
                inode = inode.left;
            } else {
                if (inode.right == null) {
                    inode.right = new IntervalNode(null, start, end, end, null);
                    return;
                }
                inode = inode.right;
            }
        }
        root =  new IntervalNode(null, start, end, end, null);
    }

    /**
     * Tests if the input interval overlaps with the existing intervals.
     * 
     * Rules:
     * 1.  If interval intersects return true. obvious.
     * 2.  if (leftsubtree == null || leftsubtree.max <=  low) go right
     * 3.  else go left
     * 
     * @param start     the start of the interval
     * @param end       the end of the interval
     * return           true if overlap, else false.
     */
    public boolean overlap(int start, int end) {
        if (start >= end) throw new IllegalArgumentException("The end " + end + " should be greater than start " + start);

        IntervalNode intervalNode = root;

        while (intervalNode != null) {
            if (intersection(start, end, intervalNode.start, intervalNode.end)) return true;

            if (goLeft(start, end, intervalNode.left)) {
                intervalNode = intervalNode.left;
            } else {
                intervalNode = intervalNode.right;
            }
        }
        return false;
    }

    /**
     * Returns if there is an intersection in the two intervals
     * Two intervals such that one of the points coincide:
     * eg: [10, 20] and [20, 40] are NOT considered as intersecting.
     */
    private boolean intersection (int start, int end, int intervalStart, int intervalEnd) {
        return start < intervalEnd && end > intervalStart;
    }

    private boolean goLeft(int start, int end, IntervalNode intervalLeftSubtree) {
        return intervalLeftSubtree != null && intervalLeftSubtree.maxEnd > start;
    }

    public static void main(String[] args) {
        IntervalSearchTree intervalSearchTree = new IntervalSearchTree();
        intervalSearchTree.add(17, 19);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(21, 24);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(4, 8);
        intervalSearchTree.add(15, 18);
        intervalSearchTree.add(7, 10);
        intervalSearchTree.add(16, 22);

        System.out.println("Expected true,   Actual: " + intervalSearchTree.overlap(23, 25));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(12, 14));
        System.out.println("Expected true,   Actual: " + intervalSearchTree.overlap(21, 23));
        // testing adjoint
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(10, 15));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(10, 14));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(11, 15));
    }
}

Answer 1

If you are testing the functionality of your code, you should create unit test. I am referencing this part of your code :

public static void main(String[] args) {
        IntervalSearchTree intervalSearchTree = new IntervalSearchTree();
        intervalSearchTree.add(17, 19);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(21, 24);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(4, 8);
        intervalSearchTree.add(15, 18);
        intervalSearchTree.add(7, 10);
        intervalSearchTree.add(16, 22);

        System.out.println("Expected true,   Actual: " + intervalSearchTree.overlap(23, 25));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(12, 14));
        System.out.println("Expected true,   Actual: " + intervalSearchTree.overlap(21, 23));
        // testing adjoint
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(10, 15));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(10, 14));
        System.out.println("Expected false,  Actual: " + intervalSearchTree.overlap(11, 15));
    }

You could use JUnit to create test classes that you could run whenever you're modifying your code. This will separate the "production" code from testing the code. A main method is typically to run your application, not test it.

I've write a test quickly out of your main :

import static org.junit.Assert.*;

import org.junit.Test;

public class IntervalSearchTreeTest {

    @Test
    public void testOverlapNormalCases() {
        IntervalSearchTree intervalSearchTree = new IntervalSearchTree();
        intervalSearchTree.add(17, 19);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(21, 24);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(4, 8);
        intervalSearchTree.add(15, 18);
        intervalSearchTree.add(7, 10);
        intervalSearchTree.add(16, 22);

        assertTrue(intervalSearchTree.overlap(23, 25));
        assertFalse(intervalSearchTree.overlap(12, 14));
        assertTrue(intervalSearchTree.overlap(21, 23));
        assertFalse(intervalSearchTree.overlap(10, 15));
        assertFalse(intervalSearchTree.overlap(10, 14));
        assertFalse(intervalSearchTree.overlap(11, 15));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testRule1Overlap() {
        IntervalSearchTree intervalSearchTree = new IntervalSearchTree();
        intervalSearchTree.add(17, 19);
        intervalSearchTree.add(5, 8);
        intervalSearchTree.add(21, 24);

        intervalSearchTree.overlap(21, 8);
    }

}

Quick tips when doing tests.

• I'll have the same package structure in my tests folder than in my sources folder.

• What I always do is naming my class with the name of the class I want to test, in this case IntervalSearchTreeTest.

• You're documentating 3 rules in overlap, there should be at least 3 tests method that verify thoses rules.

• Name you tests method with relevant name to the test. You're testing the rule 1 of overlap, well the test name should reflect it.

• Test should cover one thing only. Right now, testOverlapNormalCases looks big to me. You should shrink this one in two or more. I would probably first test when it should return true then have another test when it return false.

I'm not familiar with the algorithm so I only added the test you were doing in you main method and another one that test the obvious IllegalArgumentException throw by overlap. You should add test cases for the add method.

PS: If you're not familiar with JUnit, I strongly recommend you to read on that library.

Little note on your code :

if (intersection(start, end, intervalNode.start, intervalNode.end)) return true;

I find this line hard to read. You could at least add a newline for the return statement. It would help to see at first glance that there is an exit point at this place in the code. However, I recommend that you always add brackets.

Answer 2

Personally, I think

  if (leftsubtree != null && leftsubtree.max > low) {

is much easier to read than

  if (goLeft(start, end, intervalNode.left)) {

Also, a minor thing, you could avoid duplicating code by creating

private void checkInterval(int start, int end) {
    if (start >= end) 
    {
        throw new IllegalArgumentException("The end " + end + " should be greater than start " + start);
    }
}

Finally also a small thing: for performance sake, in overlap() you could add before the while loop a line like

if (root == null || start >= root.maxEnd || end <= root.start)
    return false;

Answer 3

It looks like IntervalSearchTree is not self-balancing. If it is not self-balancing, it will not be \$O(log(n))\$.