2026-07-22T06:37:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20448 2024-07-18T12:12:42Z ddc:004 open_access

On the Number of Distinct Fringe Subtrees in Binary Search Trees Wagner, Stephan Fringe subtrees binary search trees tree compression minimal DAG asymptotics A fringe subtree of a rooted tree is a subtree that consists of a vertex and all its descendants. The number of distinct fringe subtrees in random trees has been studied by several authors, notably because of its connection to tree compaction algorithms. Here, we obtain a very precise result for binary search trees: it is shown that the number of distinct fringe subtrees in a binary search tree with n leaves is asymptotically equal to (c₁n)/(log n) for a constant c₁ ≈ 2.4071298335, both in expectation and with high probability. This was previously shown to be a lower bound, our main contribution is to prove a matching upper bound. The method is quite general and can also be applied to similar problems for other tree models. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stephan Wagner 2024 Is Part Of LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2024.13 urn:nbn:de:0030-drops-204482 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode