Improved algorithms for ranking and unranking \((k, m)\)-ary trees in B-order

DOI10.1007/s10878-019-00469-zzbMath1498.05053WikidataQ126814426 ScholiaQ126814426MaRDI QIDQ2082174

Jou-Ming Chang, Ruay-Shiung Chang, Yu-Hsuan Chang, Ro-Yu Wu

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00469-z

zbMATH Keywords

ranking/unranking algorithms; \((k, m)\)-ary trees; Zaks' sequences; amortized cost; lexicographic/reverse-lexicographic order; RD-sequences

Mathematics Subject Classification ID

05C05: Trees

05C30: Enumeration in graph theory

68W32: Algorithms on strings

Cites Work

• A loopless algorithm for generating multiple binary tree sequences simultaneously
• Ranking and unranking of non-regular trees with a prescribed branching sequence
• \((k,m)\)-Catalan numbers and hook length polynomials for plane trees
• Lexicographic generation of ordered trees
• Gap terminology and related combinatorial properties for AVL trees and Fibonacci-isomorphic trees
• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order
• Efficient generation, ranking, and unranking of \((k,m)\)-ary trees in B-order
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A new algorithm for generation of different types of RNA
• Ranking and Unranking of AVL-Trees
• Generating trees withnnodes andmleaves
• Unnamed Item
• Unnamed Item
• Unnamed Item