Tag Archives: interval tree

Simple extensible red-black tree and interval tree implementation

For my warm up post I would like to present a small and simple (hopefully) red-black tree implementation. In my other project: AdblockTV, which I will also describe in future posts, I required an extensible balanced tree implementation that would support data structure enrichment. I checked open source libraries like guava, but I found it to be an overkill to include an entire library for just a single functionality in a relatively compact project (also guava didn’t had RangeMap class by that time). Additionally, I wanted to have a swiss knife tree implementation that I could easily enrich whenever required and writing one would be fun too. Therefore I ended up creating RedBackTree and IntervalTreeMultiSet classes. Sources can be downloaded from here.

The idea of RedBlackTree class is that it provides basic tree methods:

protected void add (Node z);
protected Node minimum (Node x);
protected Node successor (Node x);
protected void remove (Node z);
protected Node search (K key);

which operate on a tree composed of Node objects. Classes providing tree functionality must derive from the RedBlackTree class and implement own access methods. For example add(K elem) method in RedBlackTreeSet is coded below:

    public void add(K e) {
        Node node = search(e);
        if (node == getNilNode()) {
            add(new Node(e, null));
        }
    }

One can see that in this function a special method getNilNode() is called. In fact, there are two special methods in the RedBlackTree class:

protected Node getNilNode();
protected Node getRootNode();

They return Nil and Root nodes of the tree respectively.

Now, if one wants to enrich a standard red-black tree with additional data, one must derive from the RedBlackTree class. In addition, one has to define an embedded class (e.g EnrichedNode class), which derives from the RedBlackTree.Node class. Having those, one can write own access methods, which would take advantage of a balanced tree structure just like it has been done in the IntervalTreeMultiSet class. However, there are few RedBlackTree.Node methods that may need to be implemented in the example EnrichedNode class:

protected void updatePath();
protected void updateSingle();
protected void rotateUpdate();

Those methods should update enriched node data based on data from child nodes. Additionally, updatePath() should also call updateSingle() on parent nodes up to a root. Those methods are called whenever a tree structure changes and do nothing by default since we don’t want to waste CPU cycles. The reason why there are three update methods is that in a red-black tree it is not always necessary to update an entire path up to a tree root. Depending on enriched node data and operation type (e.g. nodes rotation) it might be sufficient to update just a single node and not the entire path upwards. For example, when in an IntervalTreeMultiSet instance a node is rotated with its parent, it is enough to update just that node min and max values (and not top nodes), because total min and max values in a subtree do not change. For more references, I recommend checking the IntervalTreeMultiSet itself (it is well documented). A nice feature of that class is that it supports both inclusive and exclusive intervals.