On growing random binary trees
type: Item
instance of: scholarly article
title: On growing random binary trees
zbMATH Open document ID: 0593.60014
DOI: 10.1016/0022-247X(84)90141-0
published in: Journal of Mathematical Analysis and Applications
publication date: 1984-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 3953934
zbMATH Keywords: random binary trees
zbMATH Keywords: nested binary trees
author: Boris Pittel
reviewed by: Klaus Schürger
MaRDI profile type: Publication
cites work: Q4769056
cites work: Q5659554
cites work: Q5624436
cites work: Percolation Processes and Related Topics
cites work: Postulates for subadditive processes
cites work: Q4195901
cites work: Subadditive ergodic theory
cites work: Q5585020
cites work: More Combinatorial Properties of Certain Trees
cites work: On the Most Probable Shape of a Search Tree Grown from a Random Permutation
cites work: Asymptotic Development of the Stirling Numbers of the First Kind
cites work: A Minimax Analogue of the Weak Law of Large Numbers
cites work: Limiting behavior of a process of runs
cites work: On the height of trees
cites work: On the Average Shape of Binary Trees
cites work: On the Distribution of the Number of Vertices in Strata of a Random Tree
full work available at URL: 0022-247x(84)90141-0
OpenAlex ID: W2093342130
description: scientific article; zbMATH DE number 3953934