Red-Black Trees
Self-balancing BST where each node is RED or BLACK. Guarantees O(log n) search/insert/delete.
5 Invariants
| # | Property |
|---|---|
| 1 | Every node is RED or BLACK |
| 2 | Root is BLACK |
| 3 | Every leaf (NIL) is BLACK |
| 4 | RED node has only BLACK children (no red-red) |
| 5 | All root-to-leaf paths have equal BLACK node count (black-height) |
These guarantee: longest path <= 2x shortest path, so height is O(log n).
Red-Black vs AVL
| Aspect | AVL | Re
[Description truncada. Veja o README completo no GitHub.]