Data Structures and Algorithms: Red-Black Trees

Data Structures and Algorithms

8.2 Red-Black Tree Operation

Here's an example of insertion into a red-black 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 red-black tree - there are two successive red nodes on the path
11 - 2 - 7 - 5 - 4
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 red-black 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 red-black 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 red-black tree, so we're finished!
O(logn) time!

	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 red-black tree - there are two successive red nodes on the path 11 - 2 - 7 - 5 - 4 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 red-black 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 red-black 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 red-black tree, so we're finished! O(logn) time!