Premium
The height of increasing trees
Author(s) -
Broutin N.,
Devroye L.,
McLeish E.,
de la Salle M.
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20202
Subject(s) - mathematics , tree (set theory) , combinatorics , constant (computer programming) , polynomial , weight balanced tree , struct , discrete mathematics , binary tree , computer science , mathematical analysis , binary search tree , programming language
We extend results about heights of random trees (Devroye, JACM 33 (1986) 489–498, SIAM J COMP 28 (1998) 409–432). In this paper, a general split tree model is considered in which the normalized subtree sizes of nodes converge in distribution. The height of these trees is shown to be in probability asymptotic to c log n for some constant c . We apply our results to obtain a law of large numbers for the height of all polynomial varieties of increasing trees (Bergeron et al. Lect Notes Comput Sci (1992) 24–48).© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008