We balance binary search trees to guard against adversarially-chosen inputs. But what if the data to store are random? In that case, no balancing is needed, and through a clever probabilistic analysis we can see exactly why this is.
Readings
- Luc Devroye. A Note on the Height of Binary Search Trees.
Links