Ranking and Unranking of Non-regular Trees in Gray-Code Order
A non-regular tree T with a prescribed branching sequence (s(1), s(2), ... , s(n)) is a rooted and ordered tree such that its internal nodes are numbered from I to a in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n(2)) time and O(n(2) + nS(n-1)) time, respectively, provided a preprocessing takes O(n(2)S(n-1)) time and space in advance, where Sn-1 = Sigma(n-1)(i=1)(s(i) - 1).
non-regular trees gray-code order loopless algorithms unranking algorithm ranking algorithm lexicographic order