Generation, Ranking and Unranking of Ordered Trees with Degree Bounds

Mahdi Amani
(Università di Pisa, Pisa, Italy)
Abbas Nowzari-Dalini
(UT, Tehran, Iran)

We study the problem of generating, ranking and unranking of unlabeled ordered trees whose nodes have maximum degree of Δ. This class of trees represents a generalization of chemical trees. A chemical tree is an unlabeled tree in which no node has degree greater than 4. By allowing up to Δ children for each node of chemical tree instead of 4, we will have a generalization of chemical trees. Here, we introduce a new encoding over an alphabet of size 4 for representing unlabeled ordered trees with maximum degree of Δ. We use this encoding for generating these trees in A-order with constant average time and O(n) worst case time. Due to the given encoding, with a precomputation of size and time O(n^2) (assuming Δ is constant), both ranking and unranking algorithms are also designed taking O(n) and O(nlogn) time complexities.

In César A. Muñoz and Jorge A. Pérez: Proceedings of the Eleventh International Workshop on Developments in Computational Models (DCM 2015), Cali, Colombia, October 28, 2015, Electronic Proceedings in Theoretical Computer Science 204, pp. 31–45.
Published: 2nd March 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.204.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org