Almost sure asymptotics for the random binary search tree

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publication21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PublisherDMTCS
Pages565-576
Number of pages12
Publication statusPublished - 2010
Event21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - Vienna, Austria
Duration: 27 Jun 20101 Jul 2010

Publication series

NameDMTCS Proceedings

Conference

Conference21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
CountryAustria
CityVienna
Period27/06/101/07/10

Fingerprint

Binary Search Tree
Random Permutation
Saturation
Vertex of a graph
Model

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.

Almost sure asymptotics for the random binary search tree. / Roberts, Matthew I.

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Roberts, MI 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). DMTCS Proceedings, DMTCS, pp. 565-576, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Vienna, Austria, 27/06/10.
Roberts MI. 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). DMTCS. 2010. p. 565-576. (DMTCS Proceedings).
Roberts, Matthew I. / Almost sure asymptotics for the random binary search tree. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10). DMTCS, 2010. pp. 565-576 (DMTCS Proceedings).
@inproceedings{646f2e707b234d5fa6782a4fce0fed94,
title = "Almost sure asymptotics for the random binary search tree",
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.",
author = "Roberts, {Matthew I}",
year = "2010",
language = "English",
series = "DMTCS Proceedings",
publisher = "DMTCS",
pages = "565--576",
booktitle = "21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)",

}

TY - GEN

T1 - Almost sure asymptotics for the random binary search tree

AU - Roberts, Matthew I

PY - 2010

Y1 - 2010

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

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

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0139

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0139/3334

M3 - Conference contribution

T3 - DMTCS Proceedings

SP - 565

EP - 576

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

PB - DMTCS

ER -