On growing random binary trees (Q1076401): Difference between revisions

Let \(Z=(Z_ n)\), \(n\geq 1\), be a sequence of i.i.d. random variables having a continuous distribution function, and let T be a complete infinite binary tree having root \(R_ 0\). The sequence Z and T are then used to construct a sequence of random subtrees \(t_ 1\subset t_ 2\subset...\) of T. Here, the tree \(t_ n\) has root \(R_ 0\) and n vertices labelled by \(Z_ 1,...,Z_ n\). Further let the tree \(T_ n\) be obtained from \(t_ n\) by adding to it all its direct descendants in T. Let \(h_ n\) \((H_ n)\) denote the length of the shortest (longest) path of \(T_ n.\) The main result (its proof being rather long) of the paper is that there exist two constants \(c_ 1<c_ 2\) such that the limits \[ \lim h_ n/\ln n=c_ 1,\quad \lim H_ n/\ln n=c_ 2 \] exist with probability one. This considerably strengthens a result of \textit{J. M. Robson} [The height of binary search trees. Aust. Comput. J. 11, 151-153 (1979)].