On growing random binary trees (Q1076401)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On growing random binary trees
scientific article

    Statements

    On growing random binary trees (English)
    0 references
    1984
    0 references
    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)].
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    random binary trees
    0 references
    nested binary trees
    0 references
    0 references
    0 references