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.]