Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR05-063 | 29th September 2006 00:00

Smoothed Analysis of Binary Search Trees

RSS-Feed




Revision #2
Authors: Bodo Manthey, Rüdiger Reischuk
Accepted on: 29th September 2006 00:00
Downloads: 1713
Keywords: 


Abstract:

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.<br>

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. As perturbation models, we consider partial permutations, partial alterations, and partial deletions.<br>

On the one hand, we prove tight lower and upper bounds of roughly <i>&#920;((1-p) &#8730;n/p)</i> for the expected height of binary search trees under partial permutations and partial alterations, where <i>n</i> is the number of elements and <i>p</i> is the smoothing parameter. This means that worst-case instances are rare and disappear 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 well balanced instances
can become.


Revision #1 to TR05-063 | 27th September 2005 00:00

Smoothed Analysis of Binary Search Trees





Revision #1
Authors: Bodo Manthey, Rüdiger Reischuk
Accepted on: 27th September 2005 00:00
Downloads: 1340
Keywords: 


Abstract:

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 problemsin 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. 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 &#920;(&#8730;n) for the expected height of binary search trees under partial permutations and partial alterations. This means that worst-case instances are rare and disappear 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 well balancedinstances can become.


Paper:

TR05-063 | 24th June 2005 00:00

Smoothed Analysis of the Height of Binary Search Trees





TR05-063
Authors: Bodo Manthey, Rüdiger Reischuk
Publication: 25th June 2005 12:56
Downloads: 1578
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint