@inproceedings{4d0364d5c37840a6a71992835a433ade,
title = "On the Number of Distinct Fringe Subtrees in Binary Search Trees",
abstract = "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 c1n/log n for a constant c1 ≈ 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.",
keywords = "asymptotics, binary search trees, Fringe subtrees, minimal DAG, tree compression",
author = "Stephan Wagner",
note = "Publisher Copyright: {\textcopyright} Stephan Wagner.; 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms : A of A 2024, A of A 2024 ; Conference date: 17-06-2024 Through 21-06-2024",
year = "2024",
month = jul,
doi = "10.4230/LIPIcs.AofA.2024.13",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Cecile Mailler and Sebastian Wild",
booktitle = "35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2024",
address = "Germany",
}