Research ArticleOpen AccessGoogle Scholar indexed
Counting and Randomly Generating <i>k</i>-Ary Trees
Computer and Information Science Department, Temple University, Philadelphia, USA
- 1 Computer and Information Science Department, Temple University, Philadelphia, USA
Applied Mathematics·Volume 12 (2021)·Pages 1210–1215·Published 8 December 2021·DOI10.4236/am.2021.1212077
Copy link · social · email
Abstract
k -ary trees are one of the most basic data structures in Computer Science. A new method is presented to determine how many there are with n nodes. This method gives additional insight into their structure and provides a new algo-rithm to efficiently generate such a tree randomly.
KeywordsCombinatorial Problems<i>k</i>-Ary TreesRandom Generation
- Knuth, D.E. (1998) The Art of Computer Programming. 3rd Edition, Addison-Wesley, Reading, Boston.
- Korsh, J.F. (1993) Counting and Randomly Generating Binary Trees. Information Processing Letters, 45, 291-294. https://doi.org/10.1016/0020-0190(93)90039-C
- Barcucci, E., Del Lungo, A. and Pergola, E. (1999) Random Generation of Trees and Other Combinatorial Objects. Theoretical Computer Science, 218, 219-232. https://doi.org/10.1016/S0304-3975(98)00322-3
- Korsh, J.F. (2011) Fast Generation of t-Ary Trees. The Computer Journal, 54, 776-785. https://doi.org/10.1093/comjnl/bxq025
- Drmota, M. (2009) Random Trees. Springer, Wien, New York. https://doi.org/10.1007/978-3-211-75357-6
- Knuth, D.E. (2006) The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees—History of Combinatorial Generation. Addison-Wesley, Reading, Boston.
- Wu, R.-Y., Chang, J.-M., Chan, H.-C. and Pa, K.-J. (2014) A Loopless Algorithm for Generating Multiple Binary Tree Sequences Simultaneously. Theoretical Computer Science, 556, 25-33. https://doi.org/10.1016/j.tcs.2014.07.030
- Pai, K.-J., Chang, M.C., Wu, R.-Y. and Chang, S.-C. (2019) Amortized Efficiency of Generation, Ranking and Unranking Left-Child Sequences in Lexicographic Order. Discrete Applied Mathematics, 268, 223-236. https://doi.org/10.1016/j.dam.2018.09.035
- Atkinson, M.D. and Sack, J.R. (1992) Generating Binary Trees at Random. Information Processing Letters, 41, 21-23. https://doi.org/10.1016/0020-0190(92)90075-7