# Red Black Tree

Simpler Version LLRBT Left Leaning Red Black Tree

Evaluated from: B-Tree, 2-3-4 Tree

# # Properties

- The root is black
- NULL is black (
`leaf || root.parent`

) - Red node has 2 black child
- 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

- Lemma 1: For subtree rooted at node
*x*, internal nodes $\geq \space 2^{bh(x)} - 1$

If height is 0, $2^{bh(x)} - 1 = 0$ OK

Else: todo