Compaction for two models of logarithmic‐depth trees: Analysis and experiments

DOI10.1002/rsa.21056zbMath1522.05031arXiv2005.12997OpenAlexW3210259798MaRDI QIDQ6074703

Mehdi Naima, Bernhard Gittenberger, Antoine Genitrini, Isabella Larcher, Olivier Bodini

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.12997

zbMATH Keywords

binary search treesincreasing treesanalytic combinatoricstree compactioncommon subexpression recognition

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Data structures (68P05)

Related Items

Distinct fringe subtrees in random trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• XML compression via directed acyclic graphs
• On the richness of the collection of subtrees in random binary search trees
• On the degree distribution of the nodes in increasing trees
• A quantitative study of pure parallel processes
• On the collection of fringe subtrees in random binary trees
• On the Asymptotic Probability of Forbidden Motifs on the Fringe of Recursive Trees
• An analytic approach to the height of binary search trees II
• Singularity Analysis of Generating Functions
• Random Trees
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• On the Altitude of Nodes in Random Trees
• Entropy and Optimal Compression of Some General Plane Trees
• Lossless Compression of Binary Trees With Correlated Vertex Names
• Cuts in Increasing Trees
• Repeated fringe subtrees in random rooted trees
• On Symmetries of Non-Plane Trees in a Non-Uniform Model
• Level of nodes in increasing trees revisited
• Elements of Information Theory
• The height of increasing trees