Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. Their worst-case height is linear; their average height, whose exact value is one of the best-studied problems in averagecase complexity, is logarithmic. We analyze their smoothed height under additive noise: An adversary chooses a sequence of n real numbers in the range [0, 1], each number is individually perturbed by adding a random value from an interval of size d, and the resulting numbers are inserted into a search tree. The expected height of this tree is called the smoothed tree height. If d is very small, namely for d ≤ 1/n, the smoothed tree height is the same as the worst-case height; if d is very large, the smoothed tree height approaches the logarithmic average-case height. An analysis of what happens between these extremes lies at the heart of our paper: We prove that the smoothed height of binary search trees is Θ ( p n/d + log n), where d ≥ 1/n may depend on n. This implies that the logarithmic average-case height becomes manifest for d ∈ Ω(n / log 2 n). For the analysis, we first prove that the smoothed number of left-to-right maxima in a sequence is also Θ ( p n/d + log n). We apply these findings to the performance of the quicksort algorithm and provep that the smoothed number of comparisons made by quicksort n/d + n log n). is Θ ( n d+