Simpler Version LLRBT Left Leaning Red Black Tree
Evaluated from: B-Tree, 2-3-4 Tree


  1. The root is black
  2. NULL is black (leaf || root.parent)
  3. Red node has 2 black child
  4. All paths from the node to descendant leaves contain the same number of black nodes


Lemma 13.1

A red-black tree with internal nodes has height at most
Proof Mathematical Induction

  • Lemma 1: For subtree rooted at node x, internal nodes
    If height is 0, OK
    Else: todo