×

zbMATH — the first resource for mathematics

Exact and asymptotic distributions in digital and binary search trees. (English) Zbl 0643.68077
Combinatorial relations and classical analysis are used to derive exact and asymptotic distributions for the number of steps during a successful search in digital and binary search trees.

MSC:
68P10 Searching and sorting
05A19 Combinatorial identities, bijective combinatorics
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] 1. M. ABRAMOWITZ and I. A. STEGUN, Handbook of Mathematical Functions, 1965, Dover Publications. · Zbl 0171.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.68035 MR736638 · Zbl 0529.68035 · doi:10.1287/moor.9.1.43
[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.68037 MR769900 · Zbl 0555.68037 · doi:10.1007/BF00264248
[4] 4. P. FLAJOLET, Approximate Counting: a Detailed Analysis, BIT, Vol. 25, 1985, pp. 113-134. Zbl0562.68027 MR785808 · Zbl 0562.68027 · doi:10.1007/BF01934993
[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.68041 MR850421 · Zbl 0611.68041 · doi:10.1137/0215054
[6] 6. J. FRANÇON, On the Analysis of Algorithms for Trees, Th. Comp. Sc., Vol. 4, 1977, pp. 155-169. Zbl0357.68033 MR447025 · Zbl 0357.68033 · doi:10.1016/0304-3975(77)90034-2
[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 · Zbl 0344.05103 · eudml:92037
[8] 8. D. H. GREENE and D. E. KNUTH, Mathematics for the analysis of algorithms, 1981, Birkhäuser. Zbl0481.68042 MR642197 · Zbl 0481.68042
[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. · Zbl 0605.68057
[10] 10. N. L. JOHNSON and S. KOTZ, Distribution in statistics: continuous univariate distributions, 1970, Wiley. Zbl0213.21101 · Zbl 0213.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.68053 MR864680 · Zbl 0596.68053
[12] 12. D. E. KNUTH, The Art of Computer Programming, Vol. I, 1969, Addison-Wesley. MR378456 · Zbl 0191.18001
[13] 13. D. E. KNUTH, The Art of Computer Programming, Vol. III, 1973, Addison-Wesley. MR378456 · Zbl 0191.17903
[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.68031 MR743895 · Zbl 0523.68031 · eudml:92194
[15] 15. G. LOUCHARD, Brownian Motion and Algorithms Complexity, B.I.T., Vol. 26, 1986 pp. 17-34. Zbl0602.68034 MR833828 · Zbl 0602.68034 · doi:10.1007/BF01939359
[16] 16. B. PITTEL, Paths in a Random Digital Tree: Limiting Distributions, Adv. Appl. Prob., Vol. 18, 1986, pp. 139-155. Zbl0588.60012 MR827333 · Zbl 0588.60012 · doi:10.2307/1427240
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.