Exact and asymptotic distributions in digital and binary search trees
Louchard, G.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987), p. 479-495 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1987__21_4_479_0,
     author = {Louchard, G.},
     title = {Exact and asymptotic distributions in digital and binary search trees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {21},
     year = {1987},
     pages = {479-495},
     mrnumber = {928772},
     zbl = {0643.68077},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1987__21_4_479_0}
}

Louchard, G. Exact and asymptotic distributions in digital and binary search trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) pp. 479-495. http://gdmltest.u-ga.fr/item/ITA_1987__21_4_479_0/

1. M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions, 1965, Dover Publications.

2. G. G. Brown and B. O. Shubert, On Random Binary Trees, Math. Op. Res., Vol. 9, No. 1, 1984, pp. 43-65. | MR 736638 | Zbl 0529.68035

3. L. Devroye, A Probabilistic Analysis of Height of Tries and of the Complexity of Triesort, Acta Informatica, Vol. 21, 1984, pp. 229-237. | MR 769900 | Zbl 0555.68037

4. P. Flajolet, Approximate Counting: a Detailed Analysis, BIT, Vol. 25, 1985, pp. 113-134. | MR 785808 | Zbl 0562.68027

5. P. Flajolet and R. Sedgewick, Digital Search Trees Revisited, S.I.A.M. J. Comp., Vol. 15, No. 3, 1986, pp. 748-767. | MR 850421 | Zbl 0611.68041

6. J. Françon, On the Analysis of Algorithms for Trees, Th. Comp. Sc., Vol. 4, 1977, pp. 155-169. | MR 447025 | Zbl 0357.68033

7. J. Françon, Arbres binaires de recherche : propriétés combinatoires et applications, RAIRO, Inf. Th.,Vol. 10, No. 12, 1986; pp. 35-50. | Numdam | Zbl 0344.05103

8. D. H. Greene and D. E. Knuth, Mathematics for the analysis of algorithms, 1981, Birkhäuser. | MR 642197 | Zbl 0481.68042

9. Ph. Jacquet and M. Regnier, Limiting Distributions for Trie Parameters, Proc. C.A.A.R 86, Lecture Notes in Comp. Sc, Vol. 214, 1986, pp. 198-210.

10. N. L. Johnson and S. Kotz, Distribution in statistics: continuous univariate distributions, 1970, Wiley. | Zbl 0213.21101

11. P. Kirschenhofer and H. Prodinger, Some Further Results on Digital Search Trees, Proc. I.C.A.L.R., 1986, Lect. Notes Comp. Sc., Vol. 226, pp. 177-185. | MR 864680 | Zbl 0596.68053

12. D. E. Knuth, The Art of Computer Programming, Vol. I, 1969, Addison-Wesley. | MR 378456

13. D. E. Knuth, The Art of Computer Programming, Vol. III, 1973, Addison-Wesley. | MR 378456

14. G. Louchard, The Brownian Motion: a Neglected Tool for the Complexity Analysis of Sorted Tables Manipulations, R.A.I.R.O., Inf. Th., Vol. 4, 1983, pp. 365-385. | Numdam | MR 743895 | Zbl 0523.68031

15. G. Louchard, Brownian Motion and Algorithms Complexity, B.I.T., Vol. 26, 1986 pp. 17-34. | MR 833828 | Zbl 0602.68034

16. B. Pittel, Paths in a Random Digital Tree: Limiting Distributions, Adv. Appl. Prob., Vol. 18, 1986, pp. 139-155. | MR 827333 | Zbl 0588.60012