Smoothed Analysis of Binary Search Trees

respect to the uniform distribution is only logarithmic. The exact value is one
of the best studied problems in average-case complexity.

We investigate what happens in between by analysing 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.

On the one hand, we prove tight lower and upper bounds of roughly $\sqrt{n}$
for the expected height of binary search trees under partial permutations and
partial alterations. On the other hand, we examine how much a perturbation can
increase the height of a binary search tree, i.e. how much worse well balanced
instances can become.