Stanford CS161 Lecture 7: Binary Search Trees, Red-Black Trees, and the Source of Worst-Case O(log n)
Ordinary BST operations cost O(h) and can degrade to O(n); five red-black invariants cap the height at 2 log₂(n+1), giving search, insertion, and deletion worst-case O(log n) bounds.