A LINEAR-TIME ALGORITHM FOR THE GENERATION OF TREES

Authors
ALONSO L REMY JL SCHOTT R
Citation
L. Alonso et al., A LINEAR-TIME ALGORITHM FOR THE GENERATION OF TREES, Algorithmica, 17(2), 1997, pp. 162-182
Citations number
10
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
17
Issue
2
Year of publication
1997
Pages
162 - 182
Database
ISI
SICI code
0178-4617(1997)17:2<162:ALAFTG>2.0.ZU;2-3
Abstract
We present a linear algorithm which generates randomly and with unifor m probability many kinds of trees: binary trees, ternary trees, arbitr ary trees, forests of p k-ary trees,.... The algorithm is based on the definition of generic trees which can be coded as words. These words, in turn, are generated in linear time.