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
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"
Conference_Titel :
Computer Science and Engineering Conference (ICSEC), 2015 International
DOI :
10.1109/ICSEC.2015.7401411
