Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations

DOI10.1017/S0963548308009243zbMath1159.05305MaRDI QIDQ3529509

Michael Fuchs

Publication date: 13 October 2008

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

Poisson approximationBerry-Esseen boundsrandom binary search treerandom recursive treeslimit lawnumber of subtrees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30)

Related Items (9)

Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ Limit Theorems for Subtree Size Profiles of Increasing Trees ⋮ On the size of paged recursive trees ⋮ A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees ⋮ Search trees: metric aspects and strong limit theorems ⋮ On the Subtree Size Profile of Binary Search trees ⋮ Metric dimension of critical Galton-Watson trees and linear preferential attachment trees ⋮ A non-increasing tree growth process for recursive trees and applications ⋮ Limit theorems for patterns in phylogenetic trees

Cites Work

• Asymptotic fringe distributions for general families of random trees
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• Berry-{E}sseen bounds for the number of maxima in planar regions
• A functional limit theorem for the profile of search trees
• The mean and variance of the numbers of \(r\)-pronged nodes and \(r\)-caterpillars in Yule-generated genealogical trees
• Profiles of random trees: Plane-oriented recursive trees
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• Profiles of random trees: correlation and width of random recursive trees and binary search trees
• Minimal clade size and external branch length under the neutral coalescent

This page was built for publication: Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations