| Title: |
Growing binary trees |
| Authors: |
Bodini, Olivier; Genitrini, Antoine; Nurligareev, Khaydar |
| Contributors: |
Nutritional Epidemiology Research Team; Conservatoire National des Arts et Métiers Cnam (Cnam)-Université Sorbonne Paris Nord-Centre for Research in Epidemiology and Statistics; Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Université Paris Cité (UPCité)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE); Algorithmes, Programmes et Résolution (APR); LIP6; Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS); ANR-25-CE48-0602,COMETA-GAE,COMbinatoire énumérative ET Applications: Génération Aléatoire et Exhaustive(2025); ANR-23-CE48-0014,PANDAG,Analyse de paramètres de classes de DAGS(2023) |
| Source: |
https://hal.science/hal-05562485 ; 2026. |
| Publisher Information: |
CCSD |
| Publication Year: |
2026 |
| Subject Terms: |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
| Description: |
This paper introduces a new combinatorial framework for modeling the growth of binary trees through a discrete evolution process that incorporates a growing rule and an extinction rule. Building upon the theory of increasingly labeled structures and the analysis of polynomial iterates, we extend previous models of increasing trees with label repetitions by allowing growth branches to terminate. This mechanism enables a direct connection between dynamic evolutionary processes and classical unlabeled binary trees. We provide a combinatorial outlook for this model, linking our new approach to essential but traditionally complex parameters such as tree height, the maximum number of leaves at the deepest level (for a given tree size), and the overall tree profile. Our approach reveals structural links with Mandelbrot polynomials and coding theory. Furthermore, we leverage these structural insights to develop an efficient, iterative uniform random sampler for binary trees with a prescribed profile, achieving optimal complexity in both time and space and in random bit consumption. |
| Document Type: |
report |
| Language: |
English |
| Availability: |
https://hal.science/hal-05562485; https://hal.science/hal-05562485v1/document; https://hal.science/hal-05562485v1/file/BGN26.pdf |
| Rights: |
https://creativecommons.org/licenses/by/4.0/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.40B1AF3E |
| Database: |
BASE |