We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Growing Random Uniform d-ary Trees.
- Authors
Marckert, Jean-François
- Abstract
Let T d (n) be the set of d-ary rooted trees with n internal nodes. We give a method to construct a sequence (t n , n ≥ 0) , where, for any n ≥ 1 , t n has the uniform distribution in T d (n) , and t n is constructed from t n - 1 by the addition of a new node, and a rearrangement of the structure of t n - 1 . This method is inspired by Rémy's algorithm which does this job in the binary case, but it is different from it. This provides a method for the random generation of a uniform d-ary tree in T d (n) with a cost linear in n.
- Subjects
TREES; ALGORITHMS
- Publication
Annals of Combinatorics, 2023, Vol 27, Issue 1, p51
- ISSN
0218-0006
- Publication type
Article
- DOI
10.1007/s00026-022-00621-3