|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
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!
|Back to Red Black Trees||Back to the Table of Contents|