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

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.