For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees
Ro-Yu WU Jou-Ming CHANG Sheng-Lung PENG Chun-Liang LIU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
ranking algorithms, unranking algorithms, Gray-code order, left-weight sequences, left-distance sequence,
Full Text: PDF(940.1KB)>>
Left-weight sequences (LW-sequences for short) are in common currency for encoding binary trees. In , 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.