Improved Algorithms for Ranking and Unranking (k, m)-Ary Trees

摘要

Du and Liu (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 A: 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)-axy tree of order n has exactly n crucial nodes. Recently, Amani and Nowzari-Dalini (2019) presented a generation algorithm to produce all (k,m)-ary trees of order n in B-order using Zaks' encoding, and show 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 O(kmn~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. 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. (2011), 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 O(kmn) time and O(n) space without building the precomputed table.