Explanation of Red-Black tree based implementation of TreeMap in JAVA

Question

I was going through the source code of TreeMap in JAVA. As per JAVA doc:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

In the source code I found that an Inner Class Entry was used as a node.

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        ....

As for the defination of Red-Black tree. From Wikipedia I found:

A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science.

The self-balancing is provided by painting each node with one of two colors (these are typically called 'red' and 'black', hence the name of the trees) in such a way that the resulting painted tree satisfies certain properties that don't allow it to become significantly unbalanced. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

I tried to analyse the souce code but couldn't understand the following:

1. Suppose I am already having two keys "C" and "E" in the Tree and then I am adding "D". How the nodes will be arranged (Using natural ordering).

2. How is self-balancing of Tree is implemented in the java source code.

I tried searching for detail implementationof TreeMap but was unable to find any article such as the following article I have found for HashMap

Since yesterday I am hanging on this Tree :( Can someone please help me get down...

Rivalee

Have you seen JSE sources? Everything is clear out there. – Rightward

Answer 1

1. The goal of the TreeMap is to have a tree of keys where keys that are lower than the parent's key are to the left and keys higher than the parent's key are to the right. So, if you add C, then E, you will have this tree:

   C
    \
     E
   

   If you then add D, initially you will have:

   C
    \
     E
    /
   D
   

   But this tree is unbalanced and therefore searches would be slower. So, the tree is rebalanced. After balancing, the tree now becomes much more efficient:

   C                     C
    \        rotate       \         rotate         D
     E   --- right --->    D    ---  left --->    / \
    /        around         \       around       C   E
   D           E             E        D
   

2. Rebalancing takes place inside the fixAfterInsertion() method, which checks whether the red-black properties of the tree are still maintained after insertion. And, if it doesn't, then it rebalances the tree performing either rotateLeft() or rotateRight() on the offending branch to restore the balance. Then it moves up the tree and checks the balance and so on until it reaches the root node.

There are several resources around the internet that explain Red-Black Trees in depth. But, I think the best way of understanding the process is following an animated tutorial like this: http://www.csanimated.com/animation.php?t=Red-black_tree

There is nothing peculiar in the TreeMap implementation of RBT. It closely follows the pseudocode given in CLRS's (Cormen, Leiserson, Rivest and Stein) book, which is what 99% of the implementations around do.

Scorn

I have been trying to find how is the iteration of a TreeMap done internally but havnt been able to find it online. Can you please help me understand what traversal algorithm is used to traverse the Red black tree present internally. – Facesaving

Traversal is pretty simple: take the root node as current node, if the value you're looking for is the current node, return it, otherwise if the value is lower than the current node, make the left element the current node and repeat, if the value is higher than the current node, make the right element the current node and repeat. – Scorn