Smoothed analysis of binary search trees

Bodo Manthey, Rüdiger Reischuk

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)

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.
Original languageUndefined
Pages (from-to)292-315
Number of pages24
JournalTheoretical computer science
Volume378
Issue number3
DOIs
Publication statusPublished - 2007

Keywords

  • Permutations
  • Smoothed Analysis
  • Binary search trees
  • Discrete perturbations
  • IR-79427
  • EWI-21276

Cite this