Red-Black Trees

Insertion sometimes requires the splitting of a node.
Here is an example of a splitting of a node in a red-black tree
when G is added:



Here is another example of rotating:





The code for a split and rotate are in the book on pgs 225, 226.

Now let's look at the building of a red-black
tree.