A combinatorial approach to the analysis of bucket recursive trees

作者：Kuba Markus; Panholzer Alois^*

来源：Theoretical Computer Science, 2010, 411(34-36): 3255-3273.

DOI：10.1016/j.tcs.2010.05.030

• Bucket recursive trees
• Node-depth
• Number of descendants
• Node-degree
• Limiting distribution

In this work we provide a combinatorial analysis of bucket recursive trees, which have been introduced previously as a natural generalization of the growth model of recursive trees. Our analysis is based on the description of bucket recursive trees as a special instance of the so-called bucket increasing trees, which is a family of combinatorial objects introduced in this paper. Using this combinatorial description we obtain exact and limiting distribution results for the parameter depth of a specified element, descendants of a specified element and degree of a specified element.

• 出版日期2010-7-17