# On the Horton-Strahler Number for Combinatorial Tries

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 4, page 279-296
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topNebel, Markus E.. "On the Horton-Strahler Number for Combinatorial Tries." RAIRO - Theoretical Informatics and Applications 34.4 (2010): 279-296. <http://eudml.org/doc/222082>.

@article{Nebel2010,

abstract = {
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 $$\frac\{4^\{2\beta-\alpha\}\log(\alpha)(2\beta-1)(\alpha+1)(\alpha+2)\{2\alpha+1\choose
\alpha-1\}\}\{8\sqrt\{\pi\}\alpha^\{3/2\}\log(2)(\beta-1)\beta\{2\beta\choose \beta\}^2\}$$ 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.
},

author = {Nebel, Markus E.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Horton-Strahler number; binary tries; binary trees},

language = {eng},

month = {3},

number = {4},

pages = {279-296},

publisher = {EDP Sciences},

title = {On the Horton-Strahler Number for Combinatorial Tries},

url = {http://eudml.org/doc/222082},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Nebel, Markus E.

TI - On the Horton-Strahler Number for Combinatorial Tries

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 4

SP - 279

EP - 296

AB -
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 $$\frac{4^{2\beta-\alpha}\log(\alpha)(2\beta-1)(\alpha+1)(\alpha+2){2\alpha+1\choose
\alpha-1}}{8\sqrt{\pi}\alpha^{3/2}\log(2)(\beta-1)\beta{2\beta\choose \beta}^2}$$ 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.

LA - eng

KW - Horton-Strahler number; binary tries; binary trees

UR - http://eudml.org/doc/222082

ER -

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.