Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees. (English) Zbl 1406.60120

Holmgren, Cecilia; Janson, Svante

Probab. Surv. 14, 53-154 (2017).

Summary: This survey studies asymptotics of random fringe trees and extended fringe trees in random trees that can be constructed as family trees of a Crump-Mode-Jagers branching process, stopped at a suitable time. This includes random recursive trees, preferential attachment trees, fragmentation trees, binary search trees and (more generally) \(m\)-ary search trees, as well as some other classes of random trees.
We begin with general results, mainly due to D. Aldous [Ann. Appl. Probab. 1, No. 2, 228–266 (1991; Zbl 0733.60016)] and O. Nerman and P. Jagers [Z. Wahrscheinlichkeitstheor. Verw. Geb. 65, 445–460 (1984; Zbl 0506.60084)]. The general results are applied to fringe trees and extended fringe trees for several particular types of random trees, where the theory is developed in detail. In particular, we consider fringe trees of \(m\)-ary search trees in detail; this seems to be new.
Various applications are given, including degree distribution, protected nodes and maximal clades for various types of random trees. Again, we emphasise results for \(m\)-ary search trees, and give for example new results on protected nodes in \(m\)-ary search trees.
A separate section surveys results on the height of the random trees due to L. Devroye [J. Assoc. Comput. Mach. 33, 489–498 (1986; Zbl 0741.05062)], J. D. Biggins [Ann. Appl. Probab. 5, No. 4, 1008–1024 (1995; Zbl 0859.60075); Stat. Probab. Lett. 32, No. 4, 339–342 (1997; Zbl 0904.60067)] and others.
This survey contains well-known basic results together with some additional general results as well as many new examples and applications for various classes of random trees.

MSC:

60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
60C05	Combinatorial probability
05C05	Trees
05C80	Random graphs (graph-theoretic aspects)
60J85	Applications of branching processes
68P05	Data structures
68P10	Searching and sorting

Keywords:

random trees; fringe trees; extended fringe trees; \(m\)-ary search trees; random recursive trees; preferential attachment trees; fragmentation trees; protected nodes; clades; branching processes

Citations:

Zbl 0733.60016; Zbl 0506.60084; Zbl 0741.05062; Zbl 0859.60075; Zbl 0904.60067