Red Black Trees

Rules

1. Every Node is either RED or BLACK

2. Root is always BLACK

3. New insertion are always RED

4. Every path from the root-leaf has the same number of BLACK nodes

5. No path can have two consecutive RED nodes

6. NULLs are BLACK

Rebalance

1. BLACK aunt ROTATE (BAR)
   After rotation;
   BLACK
   
     RED RED

2. RED aunt RECOLOR
   After Colorflip;
     RED

BLACK BLACK

Note: Red Black tree is a mechanism for balancing the by using the labels to tell us when to rebalance.