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

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

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A   No.6   pp.1067-1074
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1067
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
ranking algorithms,  unranking algorithms,  Gray-code order,  left-weight sequences,  left-distance sequence,  

Full Text: PDF(940.1KB)>>
Buy this Article




Summary: 
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.