Red-Black Tree — Self-Balancing with Color Invariants

The five properties

1. Every node is red or black.
2. Root is black.
3. Every leaf (NIL) is black.
4. Red nodes have black children.
5. Every root-to-leaf path has same number of black nodes.

Consequence: balanced

Max height ≤ 2 × log(N+1). Never worse than 2× perfectly balanced.

Insert violation types

Newly inserted red node with red parent violates rule 4. Fix via recoloring or rotations depending on uncle's color.

Recoloring case

If uncle is red: recolor parent + uncle black, grandparent red. Recurse up.