Campus Event Calendar

Event Entry

What and Who

Smoothed Analysis of Binary Search Trees

Bodo Manthey
Universität Lübeck
AG 1, AG 2, AG 3, AG 4, AG 5  
AG Audience

Date, Time and Location

Monday, 16 January 2006
30 Minutes
46.1 - MPII


Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with

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

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.


Benjamin Doerr
--email hidden
passcode not visible
logged in users only

Benjamin Doerr, 12/14/2005 19:35 -- Created document.