Samenvatting
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.
| Originele taal-2 | Engels |
|---|---|
| Titel | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) |
| Redacteuren | Cécile Mailler, Sebastian Wild |
| Uitgeverij | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Hoofdstuk | 10 |
| Pagina's | 10:1-10:15 |
| Aantal pagina's | 15 |
| ISBN van elektronische versie | 978-3-95977-329-4 |
| DOI's | |
| Status | Gepubliceerd - jul. 2024 |
| Evenement | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) - University of Bath, Bath, Verenigd Koninkrijk Duur: 17 jun. 2024 → 21 jun. 2024 Congresnummer: 35 |
Publicatie series
| Naam | Leibniz International Proceedings in Informatics (LIPIcs) |
|---|---|
| Volume | 302 |
Congres
| Congres | 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024) |
|---|---|
| Verkorte titel | AofA |
| Land/Regio | Verenigd Koninkrijk |
| Stad | Bath |
| Periode | 17/06/24 → 21/06/24 |
Financiering
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.