Red-Black Trees

Insertion (of Y) into a Red-Black Tree:

Before insertion


After insertion



The S,X connection goes from a 3-node to a 4 node connection.
Code on pg 221

Now let's look at a split in a red-black tree.