An Efficient Scheme for the Generation of Ordered Trees in Constant Amortized Time
Victor Parque, Tomoyuki Miyashita · 2021
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 O (n) space and 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.