Upper Bounds on the Average Height of Random Binary Trees
<|reference_start|>Upper Bounds on the Average Height of Random Binary Trees: 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 \geq 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 $\mathcal{O}(\log n)$.<|reference_end|>
@article{benkner2024upper,
    title={Upper Bounds on the Average Height of Random Binary Trees},
    author={Louisa Seelbach Benkner},
    journal={arXiv preprint arXiv:2405.17952},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.17952},
    primaryClass={math.CO cs.DM}
}