The search functionality is under construction.

Keyword Search Result

[Keyword] coding trees(1hit)

1-1hit
  • Ranking and Unranking of t-Ary Trees Using RD-Sequences

    Ro-Yu WU  Jou-Ming CHANG  Yue-Li WANG  

     
    PAPER

      Vol:
    E94-D No:2
      Page(s):
    226-232

    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.