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!
O(logn) time! |
Back to Red Black Trees | Back to the Table of Contents |