Red-Black Trees

If you insert keys 1, 2, 3, 4, 5 into a plain BST, you get a right-skewed tree that is effectively a linked list. Every search becomes O(n). Red-black trees maintain balance automatically after every insert and delete, ensuring the tree height stays O(log n) regardless of insertion order. The trade-off: every operation needs up to O(log n) recoloring steps and at most two tree rotations.

The invariants are: (1) Every node is red or black. (2) The root is black. (3) Every NULL leaf is considered black. (4) Red nodes have two black children — no two consecutive reds on any path. (5) Every path from the root to a NULL leaf contains the same number of black nodes (the "black-height"). These five rules together guarantee the longest path is at most twice the shortest path, bounding height at 2 log(n+1).

After inserting a new node (always red initially), you may violate property 4 (two consecutive reds). Fixing this involves either recoloring the parent and uncle from red to black and pushing the "redness" up the tree, or performing a rotation (left or right) to restructure a portion of the tree. The key insight: rotations are O(1) pointer operations and you perform at most two per insert or delete. Deletion is similar but has more cases.

    B              D
   / \    →      / \
  A   D        B   E
     / \      / \
    C   E    A   C

Left rotation on node B: D becomes the new subtree root

Java's TreeMap and TreeSet, and C++'s std::map and std::set are all backed by red-black trees because they need guaranteed O(log n) insertion and lookup with in-order traversal. The Linux kernel uses red-black trees in its Completely Fair Scheduler (CFS) to track runnable tasks by virtual runtime, and in the virtual memory subsystem to manage memory regions (vm_area_struct). When you need a sorted, dynamic set with predictable worst-case performance, a red-black tree is the standard answer.