@inproceedings{80705034d70d4bdca04161453cefb773,
title = "A Bijection for the Evolution of B-Trees",
abstract = "A B-tree is a type of search tree where every node (except possibly for the root) contains between m and 2m keys for some positive integer m, and all leaves have the same distance to the root. We study sequences of B-trees that can arise from successively inserting keys, and in particular present a bijection between such sequences (which we call histories) and a special type of increasing trees. We describe the set of permutations for the keys that belong to a given history, and also show how to use this bijection to analyse statistics associated with B-trees.",
keywords = "asymptotic enumeration, B-trees, bijection, histories, increasing trees, tree statistics",
author = "Fabian Burghart and Stephan Wagner",
note = "Publisher Copyright: {\textcopyright} Fabian Burghart and 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.10",
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",
}