Average Case Analysis of Leaf-Centric Binary Tree Sources

2018/04/27 by Benkner, Louisa Seelbach, Lohrey, Markus, Wagner, Stephan
#68P30 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1804.10396

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 n ≥ 2 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 Θ(n/log n), 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 Θ(n/√(log n)).

Related

• Upper Bounds on the Average Height of Random Binary Trees
• On the Collection of Fringe Subtrees in Random Binary Trees
• Fringe trees of Patricia tries and compressed binary search trees
• The Critical Beta-splitting Random Tree II: Overview and Open Problems
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees