Almost sure asymptotics for the random binary search tree
Matthew I. Roberts
Abstract
We consider a (random permutation model) binary search tree with n nodes and give asymptotics on the loglog scale for the height Hn and saturation level hn of the tree as n→∞, both almost surely and in probability. We then consider the number Fn of particles at level Hn at time n, and show that Fn is unbounded almost surely.
Full Text: PostScript PDF