Interval search tree

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:

• intersects the input arguments, it returns true.

• if (leftsubtree != null && leftsubtree.max > low) search left

• 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 e

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.

StackExchange Code Review Q#42008, answer score: 10