## Abstract

Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. We analyze their smoothed height under additive uniform noise: An adversary chooses a sequence of n real numbers in the range [0,1], each number is individually perturbed by adding a value drawn uniformly at random from an interval of size d, and the resulting numbers are inserted into a search tree. An analysis of the smoothed tree height subject to n and d lies at the heart of our paper: We prove that the smoothed height of binary search trees is (√ n/d + log n), where d ≥ 1/n may depend on n. Our analysis starts with the simpler problem of determining the smoothed number of left-to-right maxima in a sequence. We establish matching bounds, namely once more (√ n/d + log n). We also apply our findings to the performance of the quicksort algorithm and prove that the smoothed number of comparisons made by quicksort is (n/d+1 √ n/d + n log n).

Original language | English |
---|---|

Title of host publication | Mathematical Foundations of Computer Science 2008 |

Subtitle of host publication | 33rd International Symposium, MFCS 2008, Toru'n, Poland, August 25-29, 2008. Proceedings |

Editors | Edward Ochmański, Jerzy Tyszkiewicz |

Publisher | Springer |

Pages | 467-478 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-540-85238-4 |

ISBN (Print) | 978-3-540-85237-7 |

DOIs | |

Publication status | Published - 27 Oct 2008 |

Externally published | Yes |

Event | 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008: Mathematical Foundations of Computer Science - Torun, Poland, Torun, Poland Duration: 25 Aug 2008 → 29 Aug 2008 Conference number: 33 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 5162 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008 |
---|---|

Abbreviated title | MFCS 2008 |

Country/Territory | Poland |

City | Torun |

Period | 25/08/08 → 29/08/08 |

Other | August 27-31, 2008 |