• DocumentCode
    3742349
  • Title

    Ranking left-weight sequences of binary trees in gray-code order

  • Author

    Ro-Yu Wu;Jou-Ming Chang;Sheng-Lung Peng;Shun-Chieh Chang

  • Author_Institution
    Department of Industrial Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan
  • fYear
    2015
  • Firstpage
    1
  • Lastpage
    6
  • Abstract
    LW-sequences are in common currency for encoding binary trees. Wu et al. [13] 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. Based on this ordering, we propose an efficient algorithm for ranking binary trees with n internal nodes. Our algorithm can be run in O(n2) time and requires O(n) space.
  • Keywords
    "Binary trees","Encoding","Computer science","Information management","Testing","Search problems"
  • Publisher
    ieee
  • Conference_Titel
    Computer Science and Engineering Conference (ICSEC), 2015 International
  • Type

    conf

  • DOI
    10.1109/ICSEC.2015.7401411
  • Filename
    7401411
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3742349