Fish Touching🐟🎣

Red Black Tree

Apr 3, 2023

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

# Properties

  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

# Misc

# Lemma 13.1

A red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$
Proof Mathematical Induction