Pierre Lescanne - Holonomic equations and efficient random generation of binary trees

dmtcs:10952 - Discrete Mathematics & Theoretical Computer Science, February 23, 2024, vol. 25:2 - https://doi.org/10.46298/dmtcs.10952
Holonomic equations and efficient random generation of binary treesArticle

Authors: Pierre Lescanne ORCID1

  • 1 Laboratoire de l'Informatique du Parallélisme

Holonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects. Rémy showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees. I extend this paradigm to Motzkin trees and Schröder trees and show that despite slight differences my algorithm that generates random Schröder trees has linear expected complexity and my algorithm that generates Motzkin trees is in O(n) expected complexity, only if we can implement a specific oracle with a O(1) complexity. For Motzkin trees, I propose a solution which works well for realistic values (up to size ten millions) and yields an efficient algorithm.

Volume: vol. 25:2
Published on: February 23, 2024
Accepted on: July 7, 2023
Submitted on: January 23, 2024
Keywords: combinatorics,random generation,Motzkin number,Catalan number,binary tree,unary-binary tree,Schroeder number,combinatorics random generation Motzkin number Catalan number binary tree unary-binary tree,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC],[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]

Consultation statistics

This page has been seen 96 times.
This article's PDF has been downloaded 63 times.