Red-Black Trees: Balancing via Rotations

Binary Search Trees closed with a real operational risk: an ordinary, non-adversarial insertion order (e.g., chronologically arriving timestamps) can degrade a BST's height to $\Theta(n)$. A red-black tree is a BST with one extra bit of information per node (a colour, red or black) and a set of structural invariants on those colours that together guarantee $h = O(\log n)$, no matter what order keys are inserted. This note states the red-black properties, introduces rotation as the local, $O(1)$ operation used to restore them, and proves the height bound they enforce; the detailed insertion/deletion fix-up case analysis is deferred to the derivation sub-note.