IEICE Transactions on Information and Systems
Online ISSN : 1745-1361
Print ISSN : 0916-8532
Special Section on Foundations of Computer Science — Mathematical Foundations and Applications of Algorithms and Computer Science —
Ranking and Unranking of t-Ary Trees Using RD-Sequences
Ro-Yu WUJou-Ming CHANGYue-Li WANG
Author information
JOURNAL FREE ACCESS

2011 Volume E94.D Issue 2 Pages 226-232

Details
Abstract

In this paper, we introduce a concise representation, called right-distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formed sequences suggested by Zaks [Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63-82]. Using a coding tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without computing all the entries of the coefficient table.

Content from these authors
© 2011 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top