Left-leaning red-black BSTs (Guibas-Sedgewick 1979 and Sedgewick 2007)
1. Represent 2–3 tree as a BST.
2. Use "internal" left-leaning links as "glue" for 3–nodes
An equivalent definition
A BST such that:
1-1 correspondence with 2-3 trees
Key property. 1–1 correspondence between 2–3 and LLRB.
Observation. Search is the same as for elementary BST (ignore color).
Red-black BST representation
Each node is pointed to by precisely one link (from its parent) which can be encoded with color of BLACK or RED:
Elementary red-black BST operations
Left rotation. Orient a (temporarily) right-leaning red link to lean left.
Right rotation. Orient a left-leaning red link to (temporarily) lean right.
Color flip. Recolor to split a (temporary) 4-node.
Invariants. Maintains symmetric order and perfect black balance.
Insertion in a LLRB tree: overview
Basic strategy. Maintain 1-1 correspondence with 2-3 trees by applying elementary red-black BST operations.
Warmup 1. Insert into a tree with exactly 1 node.
Case 1. Insert into a 2-node at the bottom.
Warmup 2. Insert into a tree with exactly 2 nodes.
Case 2. Insert into a 3-node at the bottom.
Same code for all cases.
The complete sample code in Groovy: