Ranking and Unranking t-ary Trees in a Gray-Code Order

Abstract

A t-ary tree is a rooted tree such that every internal node has exactly t disjoint subtrees. Recently, a concise representation called right-distance sequences (RD-sequences) was introduced to represent t-ary trees and their generalization called non-regular trees. In particular, a loopless algorithm has been proposed by Wu et al. ((2010) Loopless generation of non-regular trees with a prescribed branching sequence. Comput. J., 53, 661–666) for generating non-regular trees (and thus of t-ary trees) encoded by RD-sequences in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of t-ary trees with n internal nodes. The time complexity and space requirement in both algorithms are O(max{n2,tn}) and O(tn), respectively. As a by-product, we have an improvement on ranking and unranking t-ary trees encoded by z-sequences in a Gray-code order.