Binary search trees are one of the most fundamental data structures. While the worst case height of a binary search tree is linear, the average height of binary search trees under the uniform distribution is logarithmic and one of the best studied problems in average case complexity.
We investigate what happens between worst and average case, namely the smoothed height of binary search trees: we randomly perturb a given (adversarial) sequence and then consider the height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions.
On the one hand, we prove tight lower and upper bounds of roughly Θ(√n) (in contrast to height n in the worst case and Θ(log n) on average) for the expected height of binary search trees under partial permutations and partial alterations. That means worst case instances break down under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse best case instances can become.
