Exact and asymptotic distributions in digital and binary search trees

 Access to full text

 Full (PDF)

1. 1. M. ABRAMOWITZ and I. A. STEGUN, Handbook of Mathematical Functions, 1965, Dover Publications. Zbl0171.38503
2. 2. G. G. BROWN and B. O. SHUBERT, On Random Binary Trees, Math. Op. Res., Vol. 9, No. 1, 1984, pp. 43-65. Zbl0529.68035MR736638
3. 3. L. DEVROYE, A Probabilistic Analysis of Height of Tries and of the Complexity of Triesort, Acta Informatica, Vol. 21, 1984, pp. 229-237. Zbl0555.68037MR769900
4. 4. P. FLAJOLET, Approximate Counting: a Detailed Analysis, BIT, Vol. 25, 1985, pp. 113-134. Zbl0562.68027MR785808
5. 5. P. FLAJOLET and R. SEDGEWICK, Digital Search Trees Revisited, S.I.A.M. J. Comp., Vol. 15, No. 3, 1986, pp. 748-767. Zbl0611.68041MR850421
6. 6. J. FRANÇON, On the Analysis of Algorithms for Trees, Th. Comp. Sc., Vol. 4, 1977, pp. 155-169. Zbl0357.68033MR447025
7. 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. Zbl0344.05103
8. 8. D. H. GREENE and D. E. KNUTH, Mathematics for the analysis of algorithms, 1981, Birkhäuser. Zbl0481.68042MR642197
9. 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. 10. N. L. JOHNSON and S. KOTZ, Distribution in statistics: continuous univariate distributions, 1970, Wiley. Zbl0213.21101
11. 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. Zbl0596.68053MR864680
12. 12. D. E. KNUTH, The Art of Computer Programming, Vol. I, 1969, Addison-Wesley. Zbl0191.18001MR378456
13. 13. D. E. KNUTH, The Art of Computer Programming, Vol. III, 1973, Addison-Wesley. Zbl0302.68010MR378456
14. 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. Zbl0523.68031MR743895
15. 15. G. LOUCHARD, Brownian Motion and Algorithms Complexity, B.I.T., Vol. 26, 1986 pp. 17-34. Zbl0602.68034MR833828
16. 16. B. PITTEL, Paths in a Random Digital Tree: Limiting Distributions, Adv. Appl. Prob., Vol. 18, 1986, pp. 139-155. Zbl0588.60012MR827333

1. Mireille Régnier, A limiting distribution for quicksort
2. Eric Fekete, Branching random walks on binary search trees: convergence of the occupation measure