The search functionality is under construction.

Author Search Result

[Author] Sheng-Lung PENG(1hit)

1-1hit
  • Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees

    Ro-Yu WU  Jou-Ming CHANG  Sheng-Lung PENG  Chun-Liang LIU  

     
    PAPER

      Vol:
    E99-A No:6
      Page(s):
    1067-1074

    Left-weight sequences (LW-sequences for short) are in common currency for encoding binary trees. In [16], Wu et al. proposed an algorithm associated with tree rotations for listing all binary trees in diverse representations including LW-sequences. In particular, such a list of LW-sequences is generated in Gray-code order. In this paper, based on this ordering, we present efficient ranking and unranking algorithms. For binary trees with n internal nodes, the time complexity and the space requirement in each of our ranking and unranking algorithms are O(n2) and O(n), respectively.