A bijection for the evolution of $B$-trees

Autor:	Burghart, Fabian, Wagner, Stephan
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Data Structures and Algorithms Mathematics - Probability 05A19 (Primary) 68P10 60C05 05A05 05A16 (Secondary)
Druh dokumentu:	Working Paper
Popis:	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. Comment: 17 pages, 2 figures, accepted by 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2406.06359 Zobrazit plný text záznamu View this record from Arxiv