Data Structures and Algorithms 
8.2 RedBlack Tree Operation 
Here's an example of insertion into a redblack tree (taken from Cormen, p269).
Here's the original tree .. Note that in the following diagrams, the black sentinel nodes have been omitted to keep the diagrams simple. 

The tree insert routine has just been called to insert
node "4" into the tree.
This is no longer a redblack tree 
there are two successive red nodes on the path Mark the new node, x, and it's uncle, y. y is red, so we have case 1 ... 

Change the colours of nodes 5, 7 and 8.  
Move x up to its grandparent, 7.
x's parent (2) is still red, so this isn't a redblack tree yet. Mark the uncle, y. In this case, the uncle is black, so we have case 2 ... 

Move x up and rotate left.  
Still not a redblack tree .. the uncle is black, but x's parent is to the left ..  
Change the colours of 7 and 11 and rotate right ..  
This is now a redblack tree,
so we're finished!
O(logn) time! 
Back to Red Black Trees  Back to the Table of Contents 