Average Case Analysis of Leaf-Centric Binary Tree Sources

MaRDI QIDQ6300888zbMATH OpenFDO

Authors Louisa Seelbach Benkner, Markus Lohrey, Stephan Wagner

Publication date 27 April 2018

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: We study the average number of distinct fringe subtrees in random trees generated by leaf-centric binary tree sources as introduced by Zhang, Yang and Kieffer. A leaf-centric binary tree source induces for every $ngeq2$ a probability distribution on the set of binary trees with $n$ leaves. We generalize a result by Flajolet, Gourdon, Martinez and Devroye, according to which the average number of distinct fringe subtrees in a random binary search tree of size $n$ is in $Theta(n/logn)$, as well as a result by Flajolet, Sipala and Steayert, according to which the number of distinct fringe subtrees in a uniformly random binary tree of size $n$ is in $Theta(n/sqrtlogn)$.

This page was built for publication: Average Case Analysis of Leaf-Centric Binary Tree Sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300888)