NOTE
Red-Black Tree
A self-balancing binary search tree with color invariants that keep height logarithmic.
This is a historical learning note and may contain outdated or incomplete understanding.
A red-black tree is a binary search tree with color/black-height invariants that prevent the tree from becoming excessively skewed.
Insertions/deletions use rotations and recoloring to restore invariants. The resulting height is O(log n), so search/insert/delete remain logarithmic.
Compared with stricter balancing schemes, red-black trees allow some imbalance to reduce rebalancing work while retaining a logarithmic bound.