Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-20T16:24:28.507Z Has data issue: false hasContentIssue false
  • English
  • Français

Paths in a random digital tree: limiting distributions

Published online by Cambridge University Press:  01 July 2016

Boris Pittel
Boris Pittel*
Affiliation:
The Ohio State University
*
∗Postal address: Department of Mathematics, The Ohio State University, Columbus, OH 43210, USA.
Get access Rights & Permissions [Opens in a new window]

Extract

We study a rule of growing a sequence {tn} of finite subtrees of an infinite m-ary tree T. Independent copies {ω (n)} of a Bernoulli-type process ω on m letters are used to trace out a sequence of paths in T. The tree tn is obtained by cutting each , at the first node such that at most σ paths out of , pass through it. Denote by Hn the length of the longest path, hn the length of the shortest path, and Ln the length of the randomly chosen path in tn. It is shown that, in probability, Hn – logan = O(1), hn – logb (n/log n) = 0(1), (or hn – logb (n/log log n) = O(1)), and that is asymptotically normal. The parameters a, b, c depend on the distribution of ω and, in case of a, also on σ. These estimates describe respectively the worst, the best and the typical case behavior of a ‘trie’ search algorithm for a dictionary-type information retrieval system, with σ being the capacity of a page.

Keywords

DIGITAL SEARCHHEIGHT
Type
Research Article
Information
Advances in Applied Probability , Volume 18 , Issue 1 , March 1986 , pp. 139 - 155
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Devroye, L. (1982) A note on the average depth of tries. Computing 28, 367–371.CrossRefGoogle Scholar
2. Devroye, L. (1984) A probabilistic analysis of the height of tries and of the complexity of trie sort. Acta Informatica 21, 229–237.CrossRefGoogle Scholar
3. Van Emden, M. H. (1970) Increasing the efficiency of Quicksort. CACM 13, 563–567.CrossRefGoogle Scholar
4. Fagin, R., Nievergelt, J., Pippenger, N., and Strong, H. R. (1979) Extendible hashing–a fast access method for dynamic files. ACM Trans. Database Systems 4, 315–344.CrossRefGoogle Scholar
5. Feller, W. (1970) An Introduction to Probability Theory and its Applications. Wiley, New York.Google Scholar
6. Flajolet, Ph. and Steyaert, J. M. (1982) A branching process arising in dynamic hashing, trie searching and polynomial factorization. Proc. 9th ICALP Colloquium. Lecture Notes in Computer Science 140, Springer-Verlag, New York, 239–251.Google Scholar
7. Greene, D. H. and Knuth, D. E. (1982) Mathematics for the Analysis of Algorithms. Birkhäuser, Boston.Google Scholar
8. Hurwitz, H. Jr. (1971) On the probability distribution of the values of binary trees. CACM 14, 99–102.CrossRefGoogle Scholar
9. Knuth, D. E. (1973) The Art of Computer Programming 3. Sorting and Searching. Addison-Wesley, Reading, MA.Google Scholar
10. Konheim, A. G. and Newman, D. J. (1973) A note on growing binary trees. Discrete Math. 4, 57–63.CrossRefGoogle Scholar
11. Mendelson, H. (1982) Analysis of extendible hashing. IEEE Trans. Software Engineering 8, 611–619.CrossRefGoogle Scholar
12. Pittel, B. (1985) Asymptotical growth of a class of random trees. Ann. Prob. 13, 414–427.CrossRefGoogle Scholar
13. Regnier, M. (1982) On the average height of trees in digital search and dynamic hashing. Informat. Proc. Letters 13, 64–66.CrossRefGoogle Scholar
14. Wilks, S. S. (1962) Mathematical Statistics. Wiley, New York.Google Scholar
15. Yao, A. C. (1980) A note on the analysis of extendible hashing. Informat. Proc. Letters 11, 84–86.CrossRefGoogle Scholar