Paper Info
Title
Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees
Abstract
We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio α of the level and the logarithm of tree size lies in [0,e). Convergence of all moments is shown to hold only for α ∈ [0,1] (with only convergence of finite moments when α ∈ (1,e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for α = 0 and a "quicksort type" limit law for α = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.
Year
DOI
Venue
2006
10.1007/s00453-006-0109-5
Algorithmica
Keywords
Field
DocType
Search Tree,Internal Node,Asymptotic Normality,Random Tree,Factorial Moment
Random tree,Discrete mathematics,Convergence of random variables,Combinatorics,Weak convergence,Factorial moment,Logarithm,Random binary tree,Mathematics,Binary search tree,Asymptotic distribution
Journal
Volume
Issue
ISSN
46
3
0178-4617
Citations 
PageRank 
References 
9
0.65
20
Authors
3
Name
Order
Citations
PageRank
Michael Fuchs1528.98
Hsien-Kuei Hwang236538.02
Ralph Neininger313815.56