2026-07-24T05:11:53Z https://drops.dagstuhl.de/oai

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

A Bijection for the Evolution of B-Trees Burghart, Fabian Wagner, Stephan B-trees histories increasing trees bijection asymptotic enumeration tree statistics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabian Burghart and 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.10 urn:nbn:de:0030-drops-204451 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode