...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>The Computer journal >Ranking and Unranking t-ary Trees in a Gray-Code Order
【24h】

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

机译：按格雷码顺序对三叉树进行排名和取消排名

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.)., 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{n~2, tn}) and O(tn), respectively. As a byproduct, we have an improvement on ranking and unranking t-ary trees encoded by z-sequences in a Gray-code order.
机译：三元树是一棵根树，因此每个内部节点都具有t个不相交的子树。最近，一种称为右距离序列（RD-equences）的简明表示法被引入来表示三进制树，它们的泛化称为非规则树。特别是，Wu等人提出了一种无环算法。 （（2010）使用规定的分支序列无循环生成非规则树。计算，。，53,661-666），用于生成由Gray序列中的RD序列编码的非规则树（以及t级树）。代码顺序。在本文中，基于这样的格雷码顺序，我们提出了具有n个内部节点的三进制树的有效排序和不排序算法。两种算法的时间复杂度和空间要求分别为O（max {n〜2，tn}）和O（tn）。作为副产品，我们对按格雷码顺序对由z序列编码的三进制树进行排序和不排序进行了改进。

著录项

  • 来源
    《The Computer journal》 |2013年第11期|1388-1395|共8页
  • 作者

    Ro-Yu Wu; Jou-Ming Chang; An-Hang Chen; Chun-Liang Liu;

  • 作者单位

    Department of Industrial Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan, ROC;

    Institute of Information and Decision Sciences, National Taipei College of Business, Taipei, Taiwan, ROC;

    Institute of Information and Decision Sciences, National Taipei College of Business, Taipei, Taiwan, ROC;

    Department of Humanity and Social Science, National Taiwan Normal University, Taipei, Taiwan, ROC;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    ranking algorithms; unranking algorithms; lexicographic order; Gray-code order; t-ary trees;

    机译：排名算法;排序算法;字典顺序;格雷码顺序;三元树;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号