Ranking and Unranking of Non-regular Trees in Gray-Code Order

スポンサーリンク

概要

• 論文の詳細を見る

• A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n 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(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where $S_{n-1}=\sum_{i=1}^{n-1}(s_i-1)$.

著者

• WU Ro-Yu

  Department of Industrial Management, Lunghwa University of Science and Technology

• CHANG Jou-Ming

  Institute of Information and Decision Sciences, National Taipei College of Business

• CHEN An-Hang

  Institute of Information and Decision Sciences, National Taipei College of Business

• KO Ming-Tat

  Institute of Information Science, Academia Sinica

関連論文

• Ranking and Unranking of t-Ary Trees Using RD-Sequences
• Ranking and Unranking of Non-regular Trees in Gray-Code Order

スポンサーリンク