Labels distance in bucket recursive trees with variable capacities of buckets

S. Naderi; R. Kazemi; M. H. Behzadi

doi:10.2478/ausm-2021-0025

Abstract

The bucket recursive tree is a natural multivariate structure. In this paper, we apply a trivariate generating function approach for studying of the depth and distance quantities in this tree model with variable bucket capacities and give a closed formula for the probability distribution, the expectation and the variance. We show as j → ∞, lim-iting distributions are Gaussian. The results are obtained by presenting partial differential equations for moment generating functions and solving them.

References

[1] C. Christophi, H. Mahmoud, The oscillatory distribution of distances in random tries, Ann. Appl. Probab., 15 (2005) 1536–1564.
Search in Google Scholar Back to article
[2] L. Devroye, R. Neininger, Distances and finger search in random binary search trees, SIAM J. Comput., 33 (2004), 647–658.10.1137/S0097539703424521
Search in Google Scholar Back to article
[3] R. Dobrow, On the distribution of distances in recursive trees, J. Appl. Probab., 33 (1996), 749–757.10.2307/3215356
Search in Google Scholar Back to article
[4] R. Dobrow, R. Smythe, Poisson approximations for functionals of random trees, Random Structures Algorithms, 9 (1996), 79–92.10.1002/(SICI)1098-2418(199608/09)9:1/2<79::AID-RSA5>3.0.CO;2-8
Search in Google Scholar Back to article
[5] P. Flajolet, R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge (2008).10.1017/CBO9780511801655
Search in Google Scholar Back to article
[6] R. Kazemi, Depth in bucket recursive trees with variable capacities of buckets, Act. Math. Sin, English series, 30(2) (2014), 305–310.10.1007/s10114-013-2115-2
Search in Google Scholar Back to article
[7] M. Kuba, A. Panholzer, On the distribution of distances between specified nodes in increasing trees, Discrete Appl. Math., 158 (5) (2010), 489–506.10.1016/j.dam.2009.10.014
Search in Google Scholar Back to article
[8] M. Kuba, A. Panholzer, Combinatorial approach to the analysis of bucket recursive trees. Theoret. Comput. Sci., 411 (2010), 34–36, 3253–3273.10.1016/j.tcs.2010.05.030
Search in Google Scholar Back to article
[9] H. Mahmoud, R. Neininger, Distribution of distances in random binary search trees, Ann. Appl. Probab., 13 (2003), 253–276.10.1214/aoap/1042765668
Search in Google Scholar Back to article
[10] H. Mahmoud, R. Smythe, Probabilistic analysis of bucket recursive trees. Theor. Comput. Sci., 144 (1995), 221–249.10.1016/0304-3975(94)00308-6
Search in Google Scholar Back to article
[11] A. Meir, J.W. Moon, Recursive trees with no nodes of out-degree one, Congressus Numerantium, 66 (1988), 49–62.
Search in Google Scholar Back to article
[12] J.W. Moon, The distance between nodes in recursive trees., London Mathematical Society Lecture Notes., 13 (1974), 125–132.
Search in Google Scholar Back to article
[13] A. Panholzer, The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees, Random Structures Algorithms., 25 (2004), 179–207.10.1002/rsa.20027
Search in Google Scholar Back to article
[14] A. Panholzer, H. Prodinger, Level of nodes in increasing trees revisited, Random Structures Algorithms., 31 (2007), 203–226.10.1002/rsa.20161
Search in Google Scholar Back to article

Labels distance in bucket recursive trees with variable capacities of buckets

Abstract

Paradigm

My account