The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dalam makalah ini, kami memperkenalkan perwakilan ringkas, dipanggil jujukan jarak kanan (atau singkatan jujukan RD), untuk menerangkan semua tpokok -ary dengan n nod dalaman. Hasilnya mendedahkan bahawa wujud hubungan rapat antara perwakilan dan urutan yang terbentuk dengan baik yang dicadangkan oleh Zaks [Generasi leksikografi pokok tertib, Sains Komputer secara teori 10 (1980) 63-82]. Menggunakan pokok pengekodan dan jadual bersamaan, cara yang sistematik boleh membantu kita menyiasat perwakilan struktur t-pokok ari. Akibatnya, kami membangunkan algoritma yang cekap untuk menentukan pangkat sesuatu yang diberikan tpokok -ary dalam susunan leksikografi (iaitu, algoritma pemeringkatan), dan untuk menukar integer positif kepada jujukan RD yang sepadan (iaitu, algoritma yang tidak berperingkat). Kedua-dua algoritma ranking dan unrankking boleh dijalankan dalam O(tn) masa dan tanpa mengira semua catatan jadual pekali.
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.
Salinan
Ro-Yu WU, Jou-Ming CHANG, Yue-Li WANG, "Ranking and Unranking of t-Ary Trees Using RD-Sequences" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 226-232, February 2011, doi: 10.1587/transinf.E94.D.226.
Abstract: In this paper, we introduce a concise representation, called right-distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formed sequences suggested by Zaks [Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63-82]. Using a coding tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without computing all the entries of the coefficient table.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.226/_p
Salinan
@ARTICLE{e94-d_2_226,
author={Ro-Yu WU, Jou-Ming CHANG, Yue-Li WANG, },
journal={IEICE TRANSACTIONS on Information},
title={Ranking and Unranking of t-Ary Trees Using RD-Sequences},
year={2011},
volume={E94-D},
number={2},
pages={226-232},
abstract={In this paper, we introduce a concise representation, called right-distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formed sequences suggested by Zaks [Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63-82]. Using a coding tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without computing all the entries of the coefficient table.},
keywords={},
doi={10.1587/transinf.E94.D.226},
ISSN={1745-1361},
month={February},}
Salinan
TY - JOUR
TI - Ranking and Unranking of t-Ary Trees Using RD-Sequences
T2 - IEICE TRANSACTIONS on Information
SP - 226
EP - 232
AU - Ro-Yu WU
AU - Jou-Ming CHANG
AU - Yue-Li WANG
PY - 2011
DO - 10.1587/transinf.E94.D.226
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2011
AB - In this paper, we introduce a concise representation, called right-distance sequences (or RD-sequences for short), to describe all t-ary trees with n internal nodes. A result reveals that there exists a close relationship between the representation and the well-formed sequences suggested by Zaks [Lexicographic generation of ordered trees, Theoretical Computer Science 10 (1980) 63-82]. Using a coding tree and its concomitant tables, a systematical way can help us to investigate the structural representation of t-ary trees. Consequently, we develop efficient algorithms for determining the rank of a given t-ary tree in lexicographic order (i.e., a ranking algorithm), and for converting a positive integer to its corresponding RD-sequence (i.e., an unranking algorithm). Both the ranking and unranking algorithms can be run in O(tn) time and without computing all the entries of the coefficient table.
ER -