Improved algorithms for ranking and unranking (k, m)-ary trees in B-order

Yu-Hsuan Chang, Ro-Yu Wu, Ruay-Shiung Chang and Jou-Ming Chang ()
Additional contact information
Yu-Hsuan Chang: National Taipei University of Business
Ro-Yu Wu: Lunghwa University of Science and Technology
Ruay-Shiung Chang: National Taipei University of Business
Jou-Ming Chang: National Taipei University of Business

Journal of Combinatorial Optimization, 2022, vol. 44, issue 3, No 5, 1495-1510

Abstract: Abstract Du and Liu (Eur J Comb 28:1312–1321, 2007) introduced (k, m)-ary trees as a generalization of k-ary trees. In a (k, m)-ary tree, every node on even level has degree k (i.e., has k children), and every node on odd level has degree m (which is called a crucial node) or is a leaf. In particular, a (k, m)-ary tree of order n has exactly n crucial nodes. Recently, Amani and Nowzari-Dalini (Bull Iranian Math Soc 45(4):1145–1158, 2019) presented a generation algorithm to produce all (k, m)-ary trees of order n in B-order using Zaks’ encoding, and showed that the generated ordering of this encoding results in a reverse-lexicographical ordering. They also proposed the corresponding ranking and unranking algorithms for (k, m)-ary trees according to such a generated ordering. These algorithms take $$\mathcal {O}(kmn^2)$$ O ( k m n 2 ) time and space for building a precomputed table in which (k, m)-Catalan numbers (i.e., a kind of generalized Catalan numbers) are stored in advance. Then, each ranking and unranking algorithm can be performed subsequently in $$\mathcal {O}(n)$$ O ( n ) and $$\mathcal {O}(n\log n)$$ O ( n log n ) time, respectively. In this paper, we revisit the ranking and unranking problems. With the help of an encoding scheme called “right-distance” introduced by Wu et al. (Math Comput Model 53:1331–1335, 2011a; IEICE Trans Inf Syst E94–D:226–232, 2011b), we propose new ranking and unranking algorithms for (k, m)-ary trees of order n in B-order using Zaks’ encoding. We show that both algorithms can be improved in $$\mathcal {O}(kmn)$$ O ( k m n ) time and $$\mathcal {O}(n)$$ O ( n ) space without building the precomputed table.

Keywords: (k; m)-Ary trees; Ranking/unranking algorithms; Zaks’ sequences; RD-sequences; Lexicographic/reverse-lexicographic order; Amortized cost; Primary 05c05; Secondary 68w32; 05c30 (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00469-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:3:d:10.1007_s10878-019-00469-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00469-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().