Smoothed Analysis of Binary Search Trees

While the height of binary search trees is linear in the worst case, their
average height is logarithmic. We investigate what happens in between, i.e.,
when the randomness is limited, by analyzing the smoothed height of binary
search trees: Randomly perturb a given (adversarial) sequence and then take the
expected height of the binary search tree generated by the resulting sequence.

As perturbation models, we consider partial permutations, where some elements
are randomly permuted, and additive noise, where random numbers are added to the
adversarial sequence. We prove tight bounds for the expected height of binary
search trees under these models. Furthermore, we exploit the results obtained
to get bounds for the smoothed number of comparisons that Quicksort needs.

Joint work with Ruediger Reischuk and Till Tantau (University of Luebeck).