2026-07-22T08:35:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9598 2024-03-06T10:44:30Z ddc:004 open_access

Average Case Analysis of Leaf-Centric Binary Tree Sources Seelbach Benkner, Louisa Lohrey, Markus Directed acylic graphs average case analysis tree compression We study the average size of the minimal directed acyclic graph (DAG) with respect to so-called leaf-centric binary tree sources as studied by Zhang, Yang, and Kieffer. A leaf-centric binary tree source induces for every n >= 2 a probability distribution on all binary trees with n leaves. We generalize a result shown by Flajolet, Gourdon, Martinez and Devroye according to which the average size of the minimal DAG of a binary tree that is produced by the binary search tree model is Theta(n / log n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louisa Seelbach Benkner and Markus Lohrey 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.16 urn:nbn:de:0030-drops-95982 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.16 eng https://creativecommons.org/licenses/by/3.0/legalcode