Ranking and unranking of non-regular trees with a prescribed branching sequence
✍ Scribed by Ro-Yu Wu; Jou-Ming Chang; Chir-Ho Chang
- Publisher
- Elsevier Science
- Year
- 2011
- Tongue
- English
- Weight
- 426 KB
- Volume
- 53
- Category
- Article
- ISSN
- 0895-7177
No coin nor oath required. For personal study only.
✦ Synopsis
Ordered trees are called non-regular trees with a prescribed branching sequence (or nonregular trees for short) if their internal nodes have a pre-specified degree sequence in preorder list. This article presents two main results. First, we develop a simple algorithm to generate all non-regular trees in lexicographic order using RD-sequences defined by [R.-Y. Wu, J.-M. Chang, Y.-L. Wang, Loopless generation of non-regular trees with a prescribed branching sequence, The Computer Journal 53 (2010) 661-666]. Then, by analyzing the structure of a coding tree, this algorithm is proved to run in constant amortized time. Next, we propose efficient ranking algorithm (i.e., determining the rank of a given non-regular tree in such an order) and unranking algorithm (i.e., converting a positive integer to its corresponding RD-sequence).