On the Horton-Strahler Number for Combinatorial Tries
Johann Wolfgang Goethe-Universität,
Fachbereich Informatik, Senckenbergenlage 31, 60054 Frankfurt am
Accepted: 3 October 2000
In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by provided that α and β grow in some fixed proportion ρ when α → ∞ . A similar result is shown for trees with α internal nodes but with an arbitrary number of keys.
Mathematics Subject Classification: 05A15 / 05C05 / 68W40
© EDP Sciences, 2000