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

DOI10.1007/s10878-019-00469-zzbMath1498.05053OpenAlexW2983434262WikidataQ126814426 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 treesZaks' sequencesamortized costlexicographic/reverse-lexicographic orderRD-sequences

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Improved algorithms for ranking and unranking \((k, m)\)-ary trees in B-order