Advanced Search

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\left(\alpha \right)(2\beta -1)(\alpha +1)(\alpha +2)\left(\genfrac{}{}{0pt}{}{2\alpha +1}{\alpha -1}\right)}{8\sqrt{\pi }{\alpha }^{3/2}log\left(2\right)(\beta -1)\beta {\left(\genfrac{}{}{0pt}{}{2\beta }{\beta }\right)}^2}$$ provided that and...