1 Search Results for "Lapey, Paul"

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.53

Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors: Paul Lapey and Aaron Williams

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract

The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend 𝒪(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case 𝒪(1)-time. To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one node’s stack and pushing the result onto another node’s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order. Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.

Cite as

Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lapey_et_al:LIPIcs.ISAAC.2022.53,
  author =	{Lapey, Paul and Williams, Aaron},
  title =	{{Pop \& Push: Ordered Tree Iteration in 𝒪(1)-Time}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.53},
  URN =		{urn:nbn:de:0030-drops-173380},
  doi =		{10.4230/LIPIcs.ISAAC.2022.53},
  annote =	{Keywords: combinatorial generation, Gray code, simultaneous Gray code, ordered trees, plane trees, Dyck words, binary trees, Catalan objects, loopless algorithm, cool-lex order}
}

Refine by Author
1 Lapey, Paul
1 Williams, Aaron

Refine by Classification
1 Mathematics of computing → Combinatorial algorithms
1 Mathematics of computing → Combinatorics
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Catalan objects
1 Dyck words
1 Gray code
1 binary trees
1 combinatorial generation
Show More...

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Lapey, Paul"

Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Abstract

Cite as

Thanks for your feedback!

Could not send message