论文标题
在恒定摊销时间内生成有序树的有效方案
An Efficient Scheme for the Generation of Ordered Trees in Constant Amortized Time
论文作者
论文摘要
树是有用的实体，允许在网络决策系统中对数据结构和分层关系建模。有序树是一棵根树，其中节点的子树（子树）的顺序很重要。在组合优化中，生成有序树与评估候选组合对象有关。在本文中，我们提出了一个代数计划，以最高效率生产有$ n $顶点的有序树；因此，我们的方法使用$ \ MATHCAL {O}（N）$ SPACE和$ \ MATHCAL {O}（1）平均每棵树的时间。我们的计算研究表明，在平均每毫秒的十分之一中，平均有恒定时间生成有序树的可行性和效率。由于其他组合阶层的1-1射合性质，我们的方法有利于研究具有$ n $外部节点的二进制树，带有$ n $ nodes的树木，$ n $ n $ pairs括号的法律序列，三角形的$ n $ gons，赌徒的序列和晶格路径。我们认为，我们的计划可能会发现它用于制定涉及加泰罗尼亚数字的算法进行计划和组合优化。
Trees are useful entities allowing to model data structures and hierarchical relationships in networked decision systems ubiquitously. An ordered tree is a rooted tree where the order of the subtrees (children) of a node is significant. In combinatorial optimization, generating ordered trees is relevant to evaluate candidate combinatorial objects. In this paper, we present an algebraic scheme to generate ordered trees with $n$ vertices with utmost efficiency; whereby our approach uses $\mathcal{O}(n)$ space and $\mathcal{O}(1)$ time in average per tree. Our computational studies have shown the feasibility and efficiency to generate ordered trees in constant time in average, in about one tenth of a millisecond per ordered tree. Due to the 1-1 bijective nature to other combinatorial classes, our approach is favorable to study the generation of binary trees with $n$ external nodes, trees with $n$ nodes, legal sequences of $n$ pairs of parentheses, triangulated $n$-gons, gambler's sequences and lattice paths. We believe our scheme may find its use in devising algorithms for planning and combinatorial optimization involving Catalan numbers.
