A note on the Horton-Strahler number for random binary search trees

Authors
Kruszewski, P
Citation
P. Kruszewski, A note on the Horton-Strahler number for random binary search trees, INF PROCESS, 69(1), 1999, pp. 47-51
Citations number
21
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
69
Issue
1
Year of publication
1999
Pages
47 - 51
Database
ISI
SICI code
0020-0190(19990115)69:1<47:ANOTHN>2.0.ZU;2-R
Abstract
We show that for a random binary search tree with it nodes and Horton-Strah ler number S-n, lim(n-->infinity) P{S-n greater than or equal to (1/log 3 epsilon) log n} = 0, for all epsilon > 0. This result is confirmed by the experimental results of natural scientists and explains why the random bina ry search tree model is a poor choice for modeling the combinatorial struct ure of the human lung. (C) 1999 Elsevier Science B.V. All rights reserved.