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 - Chapter in a published conference proceeding
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
T2 - 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Y2 - 27 June 2010 through 1 July 2010
ER -