Data Structures and Algorithms 
8.2 RedBlack Trees 
A redblack tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node, so that a redblack tree's node structure would be:
struct t_red_black_node { enum { red, black } colour; void *item; struct t_red_black_node *left, *right, *parent; }For the purpose of this discussion, the NULL nodes which terminate the tree are considered to be the leaves and are coloured black.


A basic redblack tree  
Basic redblack tree with the
sentinel nodes added.
Implementations of the redblack tree algorithms will usually include
the sentinel nodes as a convenient means of flagging that you have
reached a leaf node. They are the NULL black nodes of property 2. 
This demonstrates why the redblack tree is a good search tree: it can always be searched in O(log n) time.
As with heaps, additions and deletions from redblack trees destroy the redblack property, so we need to restore it. To do this we need to look at some operations on redblack trees.
A rotation is a local operation
in a search tree that preserves
inorder traversal key ordering.
Note that in both trees, an inorder traversal yields:
A x B y C 
left_rotate( Tree T, node x ) { node y; y = x>right; /* Turn y's left subtree into x's right subtree */ x>right = y>left; if ( y>left != NULL ) y>left>parent = x; /* y's new parent was x's parent */ y>parent = x>parent; /* Set the parent to point to y instead of x */ /* First see whether we're at the root */ if ( x>parent == NULL ) T>root = y; else if ( x == (x>parent)>left ) /* x was on the left of its parent */ x>parent>left = y; else /* x must have been on the right */ x>parent>right = y; /* Finally, put x on y's left */ y>left = x; x>parent = y; }
rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the redblack property */ x>colour = red; while ( (x != T>root) && (x>parent>colour == red) ) { if ( x>parent == x>parent>parent>left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x>parent>parent>right; if ( y>colour == red ) { /* case 1  change the colours */ x>parent>colour = black; y>colour = black; x>parent>parent>colour = red; /* Move x up the tree */ x = x>parent>parent; } else { /* y is a black node */ if ( x == x>parent>right ) { /* and x is to the right */ /* case 2  move x up and rotate */ x = x>parent; left_rotate( T, x ); } /* case 3 */ x>parent>colour = black; x>parent>parent>colour = red; right_rotate( T, x>parent>parent ); } } else { /* repeat the "if" part with right and left exchanged */ } } /* Colour the root black */ T>root>colour = black; }
Here's an example of the insertion operation.
RedBlack Tree Animation This animation was written by Linda Luo, Mervyn Ng, Anita Lee, John Morris and Woi Ang. 

Please email comments to: morris@ee.uwa.edu.au 
Examination of the code reveals only one loop. In that loop, the node at the root of the subtree whose redblack property we are trying to restore, x, may be moved up the tree at least one level in each iteration of the loop. Since the tree originally has O(log n) height, there are O(log n) iterations. The tree_insert routine also has O(log n) complexity, so overall the rb_insert routine also has O(log n) complexity.
Key terms 
Continue on to AVL Trees  Back to the Table of Contents 