2024/05/28 by Louisa Seelbach Benkner, Benkner, Louisa Seelbach
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2405.17952
openalex publication_date 2024/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the average height of 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. Our results generalize a result by Devroye, according to which the average height of a random binary search tree of size n is in O(log n).