### Abstract

We consider a (random permutation model) binary search tree with n nodes and give asymptotics on the loglog scale for the height H_n and saturation level h_n of the tree as n\to\infty, both almost surely and in probability. We then consider the number F_n of particles at level H_n at time n, and show that F_n is unbounded almost surely.

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

Title of host publication | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) |

Publisher | DMTCS |

Pages | 565-576 |

Number of pages | 12 |

Publication status | Published - 2010 |

Event | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - Vienna, Austria Duration: 27 Jun 2010 → 1 Jul 2010 |

### Publication series

Name | DMTCS Proceedings |
---|

### Conference

Conference | 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) |
---|---|

Country | Austria |

City | Vienna |

Period | 27/06/10 → 1/07/10 |

## Fingerprint Dive into the research topics of 'Almost sure asymptotics for the random binary search tree'. Together they form a unique fingerprint.

## Cite this

Roberts, M. I. (2010). Almost sure asymptotics for the random binary search tree. In

*21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)*(pp. 565-576). (DMTCS Proceedings). DMTCS.