Fish Touching🐟🎣

Left Leaning Red Black Tree

Apr 3, 2023

# 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.

# 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

# Criticism

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.