Ranking and Unranking of t-Ary Trees Using RD-Sequences

摘要

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 f-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.