IEICE TRANSACTIONS on Fundamentals
Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1067-1074
- Publication Date
- 2016/06/01
- Publicized
- 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
Authors
Ro-Yu WU
Lunghwa University of Science and Technology
Jou-Ming CHANG
National Taipei University of Business
Sheng-Lung PENG
National Dong Hwa University
Chun-Liang LIU
National Taiwan Normal University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ro-Yu WU, Jou-Ming CHANG, Sheng-Lung PENG, Chun-Liang LIU, "Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1067-1074, June 2016, doi: 10.1587/transfun.E99.A.1067.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1067/_p
Copy
@ARTICLE{e99-a_6_1067,
author={Ro-Yu WU, Jou-Ming CHANG, Sheng-Lung PENG, Chun-Liang LIU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees},
year={2016},
volume={E99-A},
number={6},
pages={1067-1074},
abstract={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.},
keywords={},
doi={10.1587/transfun.E99.A.1067},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Gray-Code Ranking and Unranking on Left-Weight Sequences of Binary Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1067
EP - 1074
AU - Ro-Yu WU
AU - Jou-Ming CHANG
AU - Sheng-Lung PENG
AU - Chun-Liang LIU
PY - 2016
DO - 10.1587/transfun.E99.A.1067
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - 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.
ER -
English
