The height of increasing trees | Zendy

Broutin N. | Zendy; Devroye L. | Zendy; McLeish E. | Zendy; de la Salle M. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 , combinatorics , tree (set theory) , constant (computer programming) , polynomial , discrete mathematics , struct , random tree , mathematical analysis , computer science , artificial intelligence , programming language , motion planning , robot

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research