A linear Time Algorithm for the Generation of Trees

Abstract : We present a linear algorithm which generates randomly and with uniform probability many kinds of trees: binary trees, ternary trees, arbitrary trees, forests of $p$ $k$-ary trees, $\ldots$. 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.
Type de document :
Rapport
[Research Report] RR-2934, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073765
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:42:41
Dernière modification le : samedi 17 septembre 2016 - 01:06:50
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:57:34

Fichiers

Identifiants

  • HAL Id : inria-00073765, version 1

Collections

Citation

Laurent Alonso, Jean-Luc Rémy, René Schott. A linear Time Algorithm for the Generation of Trees. [Research Report] RR-2934, INRIA. 1996. 〈inria-00073765〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

138