Left Leaning Red Black Tree

Properties

1. Represent 2-3-4 Tree as a Tree.
2. Use “internal” red edges for 3- and 4- nodes.
3. Require that 3-nodes be left-leaning.
   

• Disallowed
  1. right-leaning 3-node representation
     
  2. two reds in a row
     

How to

1. In Red-Black Tree, we only rotate red links (to maintain perfect black-link balance)
   • Left Rotate
     • 
   • Right Rotate
     • 
2. Then we maintain preperties
   • Color flip to split 4-node
     • 
     • 
     • 
   • left-rotate any right-leaning link on search path
   • right-rotate top link if two reds in a row found
   • trivial with recursion (do it after recursive calls)
   • no corrections needed elsewhere
3. Insert
   1. At the bottom
      
   2. Split a 4-node
      
   3. Enforce left-leaning condition
      
   4. Balance a 4-node
      
   5. Complete Code (A top-down 2-3-4 nodes tree)
      
   6. If we move the color-flipping precedure to the bottom, it becomes a bottom-up 2-3 nodes tree

Links

• Java Code

Criticism

• LLRB is BAD

Sedgewick’s paper is tricky. As of 2013, the insert section presents 2–3–4 trees as the default and describes 2–3 trees as a variant. The delete implementation, however, only works for 2–3 trees. If you implement the default variant of insert and the only variant of delete, your tree won’t work. The text doesn’t highlight the switch from 2–3–4 to 2–3: not kind.