A NOTE ON THE HORTON-STRAHLER NUMBER FOR RANDOM TREES

Authors
DEVROYE L KRUSZEWSKI P
Citation
L. Devroye et P. Kruszewski, A NOTE ON THE HORTON-STRAHLER NUMBER FOR RANDOM TREES, Information processing letters, 56(2), 1995, pp. 95-99
Citations number
17
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
56
Issue
2
Year of publication
1995
Pages
95 - 99
Database
ISI
SICI code
0020-0190(1995)56:2<95:ANOTHN>2.0.ZU;2-Y
Abstract
We consider the Horton-Strahler number S-n for random equiprobable bin ary trees with n nodes. We give a simple probabilistic proof of the we ll-known result that ES(n) = log(4) n + O(1) and show that for every x > 0, P{\S-n - log(4) n\ greater than or equal to x} less than or equa l to D/4(x), for some constant D > 0.