# Smoothed analysis of binary search trees

Manthey, Bodo
and
Reischuk, Rüdiger
(2007)
*Smoothed analysis of binary search trees.*
Theoretical Computer Science, 378
(3).
pp. 292-315.
ISSN 0304-3975

PDF
Restricted to UT campus only : Request a copy 423kB |

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

Item Type: | Article |

Copyright: | © 2007 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/79427 |

Official URL: | http://dx.doi.org/10.1016/j.tcs.2007.02.035 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page