Ranking and Unranking t-ary Trees in a Gray-Code Order
Ranking and Unranking t-ary Trees in a Gray-Code Order
复制标题
按格雷码顺序对 t 叉树进行排序和取消排序
DOI：
10.1093/comjnl/bxs143
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Chun
中科院分区：
文献类型：
--
作者：
Ro;Jou;An;Chun
一棵t叉树是一棵有根树，使得每个内部节点都有t个不相交的子树。最近，一个简洁的表示称为右距离序列（RD-序列）被引入到表示的t-ary树和他们的推广称为非正则树。特别地，无环算法已经由Wu等人提出（（2010）Loopless generation of non-regular trees with a prescribed branching sequence. Comput. J.，53，661-666），用于生成以格雷码顺序由RD序列编码的非规则树（并且因此生成t叉树）。本文基于这种格雷码序，给出了具有n个内部结点的t叉树的有效排序和去排序算法。两种算法的时间复杂度和空间需求分别为O（max{n2，tn}）和O（tn）。作为一个副产品，我们有一个改进的排名和unranking的t-ary树编码的z-序列在格雷码的顺序。
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.