Red-black tree
Self-balancing binary search tree with "colour" invariants — Rudolf Bayer 1972, named by Leonidas Guibas (1978). The most common choice in standard libraries.
Five rules guarantee O(log n) depth without balancing as strictly as AVL. Result: faster insert/delete than AVL, marginally slower lookup. Operations require rotations + recolouring.
Powers C++ std::map, Java TreeMap/TreeSet, the Linux Completely Fair Scheduler, Linux epoll, many network-stack implementations. Competitor: B-tree (for disk), AVL (lookup-heavy workloads), Skip list (simpler lock-free implementation).