Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Discrete Perturbations:
TR05-063 | 24th June 2005
Bodo Manthey, RĂ¼diger Reischuk

Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

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

ISSN 1433-8092 | Imprint