What height bound does a red-black tree guarantee, and what does it buy?

Answer

h ≤ 2 lg(n+1) = O(lg n); all dynamic-set operations are O(lg n) worst-case

Properties 4 and 5 cap the longest path at twice the shortest, so height stays logarithmic regardless of insertion order — fixing the BST degeneracy problem.