Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees
Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees
复制标题
边缘树、Crump-Mode-Jagers 分支过程和 $m$-ary 搜索树
DOI：
10.1214/16-ps272
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Janson
中科院分区：
文献类型：
--
作者：
Cecilia Holmgren;S. Janson
本文研究了随机树中的随机条纹树和扩展条纹树的渐近性，这些树可以构造为在适当时间停止的Crump-Mode-Jagers分支过程的家族树。这包括随机递归树、优先连接树、碎片树、二叉搜索树和（更普遍的）$m$-ary搜索树，以及一些其他类型的随机树。
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 Aldous (1991) and Jagers and Nerman (1984). 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 height, saturation level, typical depth and total path length, due to Devroye (1986), Biggins (1995, 1997) 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.