Abstract
Distances between nodes in random trees is a popular topic, and several classes of trees have recently been investigated. We look into this matter in digital search trees. By analytic techniques, such as the Mellin Transform and poissonization, we describe a program to determine the moments of these distances. The program is illustrated on the mean and variance. One encounters delayed Mellin transform equations, which we solve by inspection. In addition to various asymptotics, we give an exact expression for the mean and for the variance in the unbiased case. Interestingly, the unbiased case gives a bounded variance, whereas the biased case gives a variance growing with the number of keys. It is therefore possible in the biased case to show that an appropriately normalized version of the distance converges to a limit. The complexity of moment calculation increases substantially with each higher moment; it is prudent to seek a shortcut to the limit via a method that avoids the computation of all moments. Toward this end, we utilize the contraction method to show that in biased digital search trees the distribution of a suitably normalized version of the distances approaches a limit that is the fixed-point solution of a distributional equation (distances being measured in the Wasserstein metric space). An explicit solution to the fixed-point equation is readily demonstrated to be Gaussian.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aguech R., Lasmar N., Mahmoud H. (2006) Limit distribution of distances in biased random tries. J. Appl. Probab. 43, 1–14
Chern H., Hwang H., Tsai T. (2002) An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms. J. Algorithms 44, 177–225
Christophi C., Mahmoud H. (2005) The oscillatory distribution of distances in random tries. Ann. Appl. Probab. 15, 1536–1564
Coffman E., Eve J.: File structures using hashing functions. Commun. ACM 13, 427–432, and 436 (1970)
Devroye L., Neininger R. (2004) Distances and finger search in random binary search trees. SIAM J. Comput. 33, 647–658
Flajolet P., Sedgewick R. (1986) Digital search trees revisited. SIAM J. Comput. 15, 748–767
Flajolet P., Gourdon X., Dumas P. (1995) Mellin transform and asymptotic harmonic sums. Theor. Comput. Sci. 144, 3–58
Gutman I., Polansky O. (1986) Mathematical Concepts in Organic Chemistry. Springer, Berlin Heidelberg New York
Jacquet P.: Contribution de l’Analyse d’Algorithmes a l’Evaluation de Protocoles de Communication. Thèse Université de Paris Sud-Orsay, Paris (1989)
Jacquet P., Szpankowski W. (1998) Analytical depoissonization and its applications. Theor. Comput. Sci. 201, 1–62
Kirschenhofer P., Prodinger H. (1988) Further results on digital search trees. Theor. Comput. Sci. 58, 143–154
Kirschenhofer P., Prodinger H., Szpankowski W. (1994) Digital search trees again revisited: the internal path length perspective. SIAM J. Comput. 23, 598–616
Knuth D. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Addison-Wesley, Reading, MA (1998)
Louchard G. (1987) Exact and asymptotic distributions in digital and binary search trees. RAIRO: Theor. Informat. Appl. 21, 479–495
Louchard G., Szpankowski W. (1995) Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm. IEEE Trans. Informat. Theory 41, 478–488
Louchard G., Szpankowski W., Tang J. (1999) Average profile of the generalized digital-search tree and the generalized Lempel-Ziv algorithms. SIAM J. Comput. 28, 935–954
Mahmoud H. (1992) Evolution of Random Search Trees. Wiley, New York
Mahmoud M., Neininger R. (2003) Distribution of distances in random binary search trees. Ann. Appl. Probab. 13, 253–276
Mathys P., Flajolet P. (1985) Q-ary collision resolution algorithms in random-access systems with free and blocked channel access. IEEE Trans. Informat. Theory 31, 217–243
Neininger R. (2001) On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Struct. Algorithms 19, 498–524
Neininger R. (2002) The Wiener index of random trees. Combinat. Probab. Comput. 11, 587–597
Neininger R., Rüschendorf L. (2004) A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14, 378–418
Panholzer A., Prodinger H. (2004) Spanning tree size in random binary search trees. Ann. Appl. Probab. 14, 718–733
Pittel B. (1985) Asymptotical growth of a class of random trees. Ann. Probab. 13, 414–427
Rachev S., Rüschendorf L. (1995) Probability metrics and recursive algorithms. Adv. Appl. Probab. 27, 770–799
Rösler U. (1991) A limit theorem for “Quicksort”. RAIRO Inform. Théor. Appl. 25, 85–100
Rösler U. (2001) On the analysis of stochastic divide and conquer algorithms. Algorithmica, 29, 238–261
Rösler U., Rüschendorf L. (2001) The contraction method for recursive algorithms. Algorithmica 29, 3–33
Schachinger W.: Beiträge zur Analyse von Datenstrukturen zur Digitalen Suche. Dissertation Technische Universität Wien, Vienna (1993)
Szpankowski W. (1991) A characterization of digital search trees from the successful search viewpoint. Theor. Comput. Sci. 85, 117–134
Szpankowski W. (2001) Average Case Analysis of Algorithms on Sequences. Wiley, New York
Trinajstić N. (1992) Chemical Graph Theory. CRC Press, Boca Raton FL
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Aguech, R., Lasmar, N. & Mahmoud, H. Distances in random digital search trees. Acta Informatica 43, 243–264 (2006). https://doi.org/10.1007/s00236-006-0019-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-006-0019-7