Labels distance in bucket recursive trees with variable capacities of buckets

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.

Keywords

• bucket recursive trees
• trivariate generating function
• partial differential equations
• depth
• distance
• 60f05
• 05c05