Comment on page

18.3 Inserting LLRB Trees

Some Tree Maintenance.
We can always insert into an LLRB tree by inserting into a 2-3 tree and converting it as we've done before. However, this would be contrary to our original purpose of creating LLRBs, which was to avoid the complicated implementation of a 2-3 tree!
Instead, we insert into the LLRB as we would with a normal BST. However, this could break its 1-1 mapping to a 2-3 tree, so we will use rotations to massage the tree back into a proper structure.

Maintaining Proper Structure

When inserting into an LLRB tree, we always insert the new node with a red link to its parent node. This is because in a 2-3 tree, we are always inserting by adding to a leaf node, the color of the link we add should always be red.
But sometimes, inserting red links at certain places might lead to cases where we break one of the invariants of LLRBs.
Below are three such cases where we need to perform certain tasks address in order to maintain the LLRB tree's proper structure:
• Case 1: Insertion results in a right leaning "3-node -> Left Leaning Violation
• Recall, we are using left-leaning red black trees, which means we can never have a right red link.
• To address this, we will need to use a rotation in order to maintain the LLRB invariant: "There are no right red links".
• If the left child is also a red link, then we will temporarily allow it for purposes that will become clearer in case 2.
Case 1: Inserting a Right Red Link
• Case 2: Double Insertion on the Left -> Incorrect 4 Node Violation
• If there are 2 left red links, then we have a 4-node which is illegal.
• To address this, we will first rotate to create the same tree seen in case 1 above. Then, in both situations, we will address the temporary issue of having an illegal 4-node in case 3.
Case 2: Double Insertion on the Left
• Case 3: Node has Two Red Children -> Temporary 4 Node
• Finally, to address the issue of having illegal 4-node by flipping the colors of all edges touching "S" above.
• This is equivalent to pushing up the middle node in a 2-3 tree.