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.
Original language | English |
---|---|
Title of host publication | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) |
Editors | Cécile Mailler, Sebastian Wild |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Chapter | 10 |
Pages | 10:1-10:15 |
Number of pages | 15 |
ISBN (Electronic) | 978-3-95977-329-4 |
DOIs | |
Publication status | Published - Jul 2024 |
Event | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) - University of Bath, Bath, United Kingdom Duration: 17 Jun 2024 → 21 Jun 2024 Conference number: 35 |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 302 |
Conference
Conference | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) |
---|---|
Abbreviated title | AofA |
Country/Territory | United Kingdom |
City | Bath |
Period | 17/06/24 → 21/06/24 |
Funding
Fabian Burghart: F. Burghart has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie Grant Agreement No 101034253. Stephan Wagner: Supported by the Swedish research council (VR), grant 2022-04030.
Keywords
- B-trees
- asymptotic enumeration
- bijection
- histories
- increasing trees
- tree statistics