On the Horton-Strahler number for random tries

L. Devroye; P. Kruszewski

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 5, page 443-456
  • ISSN: 0988-3754

How to cite


Devroye, L., and Kruszewski, P.. "On the Horton-Strahler number for random tries." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.5 (1996): 443-456. <http://eudml.org/doc/92545>.

author = {Devroye, L., Kruszewski, P.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Horton-Strahler number},
language = {eng},
number = {5},
pages = {443-456},
publisher = {EDP-Sciences},
title = {On the Horton-Strahler number for random tries},
url = {http://eudml.org/doc/92545},
volume = {30},
year = {1996},

AU - Devroye, L.
AU - Kruszewski, P.
TI - On the Horton-Strahler number for random tries
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 5
SP - 443
EP - 456
LA - eng
KW - Horton-Strahler number
UR - http://eudml.org/doc/92545
ER -


  1. 1 A. V. AHO. , J. E. HOPCROFT and J. D. ULLMAN, Data Structures and Algorithms, Addison-Wesley, Reading, MA, 1983. Zbl0487.68005MR666695
  2. 2 D. ARQUÈS, N. JANEY and X. G. VIENNOTModélisation de la croissance et de la forme de structures arborescentes par matrice d'évolution. In Actes de MICAD'91, Paris, 1991, pp. 321-336. 
  3. 3. L. DEVROYE, A note ontheprobabilistic analysis of Patricia trees, Random Structures and Algorithms, 1992, 3, pp. 203-214 Zbl0768.05083MR1151362
  4. 4. L. DEVROYE and P. KRUSZEWSKI, A note on the Horton-Strahler number for random trees, Information Processing Letters, 1994, 52, pp. 155-159. Zbl0809.05031MR1302588
  5. 5. A. P. ERSHOV, On programming of arithmetic operations, Communications of the ACM, 1958, 1, pp. 3-6. Zbl0086.33203
  6. 6. R. FAGIN, J. NIEVERGELT, N. PIPPENGER and H. R. STRONG, Extendible hashing - a fast access method for dynamic files, ACM Transactions on Database Systems, 1979, 4, pp. 315-344. 
  7. 7. P. FLAJOLET, J. C. RAOULT and J. VUILLEMIN, The number of registers required for evaluating arithmetic expressions, Theoretical Computer Science, 1979, 9, pp. 99-125. Zbl0407.68057MR535127
  8. 8. J. FRANÇON, Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique, RAIRO Theoretical Informatics, 1984, 18, pp. 355-364. Zbl0547.68041MR775838
  9. 9. E. H. FREDKIN, Trie memory, Communications of the ACM, 1960, 3, pp. 490-500. 
  10. 10. W. HOEFFDING, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 1963, 58, pp. 13-30. Zbl0127.10602MR144363
  11. 11. R. E. HORTON, Erosional development of streams and their drainage basins; hydrophysical approach to quantitative morphology, Bulletin of the Geological Society of America, 1945, 56, pp. 275-370. 
  12. 12. P. JACQUET and W. SZPANKOWSKI, Analysis of digital tries with Markovian dependency, IEEE Transactions on Information Theory, 1991, IT37, pp. 1470-1475. 
  13. 13. R. KEMP, The average number of registers needed to evaluate a binary tree optimally, Acta Informatica, 1979, 11, pp. 363-372. Zbl0395.68059MR533482
  14. 14. D. E. KNUTH, The Art of Computer Programming. Sorting and Searching, volume 3, Addison-Wesley, Reading, MA, 1973. Zbl0302.68010MR378456
  15. 15. P. KRUSZEWSKI, A probabilistic exploration of the Horton-Strahler number for random binary trees, Master's thesis, School of Computer Science, McGill University, 1993. 
  16. 16. P. A. LARSON, Dynamic hashing. BIT, 1978, 75, pp. 184-201. Zbl0377.68026MR483823
  17. 17. W. LITWIN, Trie hashing. In Proceedings of the ACM - SIGMOD Conf. MOD., Ann Arbor, Michigan, 1981. 
  18. 18. A. MEIR and J. W. MOON, Stream lengths in random channel networks, Congressus Numerantium, 1980, 33, pp. 25-33. Zbl0496.94020MR681917
  19. 19. A. MEIR, J. W. MOON and J. R. POUNDER, On the order of random channel networks, SIAM Journal of Algebraic and Discrete Methods, 1980, 1, pp. 25-33. Zbl0496.94020MR563011
  20. 20. J. W. MOON, On Horton's law for random channel networks, Annals of Discrete Mathematics, 1980, 8, pp. 117-121. Zbl0443.05035MR597163
  21. 21. J. G. PENAUD, Matrice de ramification des arbres binaires, Discrete Applied Mathematics, 1991, 31, pp. 1-21. Zbl0732.05038MR1097523
  22. 22. B. PITTEL, Asymptotic growth of a class of random trees, Annals of Probability, 1985, 18, pp. 414-427. Zbl0563.60010MR781414
  23. 23. H. PRODINGER, Solution of a problem of Yekutieli and Mandelbrot, Technical report, Technical University of Vienna, Austria, 1995. 
  24. 24. A. N. STRAHLER, Hypsometric (area-altitude) analysis of erosional topology, Bulletin of the Geological Society of America, 1952, 63, pp. 1117-1142. 
  25. 25. J. VANNIMENUS and X. G. VIENNOT, Combinatorial Tools for the Analysis of Ramified Patterns, Journal of Statistical Physics, 1989, 54, pp. 1529-1539. MR993071
  26. 26. M. VAUCHAUSSADE de CHAUMONT, Nombre de Strahler des arbres, langages algébriques et dénombrement des structures secondaires en biologie moléculaire, PhD thesis, Université de Bordeaux I, 1985. 
  27. 27. M. VAUCHAUSSADE de CHAUMONT and X. G. VIENNOT, Enumeration of RNAs secondary structures by complexity, Mathematics in Medicine and Biology, Lecture Notes in Biomathematics, 1985, 57, pp. 360-365. Zbl0579.92012
  28. 28. X. G. VIENNOT, Trees everywhere. In A. Arnold ed., Proceedings of the 15th Colloquium on Trees in Algebra and Programming, Copenhagen, Denmark, May 15-18, 1990, Lecture Notes in Computer Science, Springer-Verlag, Berlin 1990, volume 431, pp. 18-41. Zbl0785.68092MR1075020
  29. 29. X. G. VIENNOT, G. EYROLLES, N. JANEY and D. ARQUÈS, Combinatorial analysis of ramified pattems and computer imagery of trees. In Proceedings of SIGGRAPH'89, Computer Graphics, 1989, volume 23, pp. 31-40. 

NotesEmbed ?


You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.