A note on the asymptotic behavior of the heights in \(b\)-trees for \(b\) large
The electronic journal of combinatorics, Tome 7 (2000)
We study the limiting distribution of the height in a generalized trie in which external nodes are capable to store up to $b$ items (the so called $b$-tries). We assume that such a tree is built from $n$ random strings (items) generated by an unbiased memoryless source. In this paper, we discuss the case when $b$ and $n$ are both large. We shall identify five regions of the height distribution that should be compared to three regions obtained for fixed $b$. We prove that for most $n$, the limiting distribution is concentrated at the single point $k_1=\lfloor \log_2 (n/b)\rfloor +1$ as $n,b\to \infty$. We observe that this is quite different than the height distribution for fixed $b$, in which case the limiting distribution is of an extreme value type concentrated around $(1+1/b)\log_2 n$. We derive our results by analytic methods, namely generating functions and the saddle point method. We also present some numerical verification of our results.
@article{10_37236_1517,
author = {Charles Knessl and Wojciech Szpankowski},
title = {A note on the asymptotic behavior of the heights in \(b\)-trees for \(b\) large},
journal = {The electronic journal of combinatorics},
year = {2000},
volume = {7},
doi = {10.37236/1517},
zbl = {0949.68057},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1517/}
}
TY - JOUR AU - Charles Knessl AU - Wojciech Szpankowski TI - A note on the asymptotic behavior of the heights in \(b\)-trees for \(b\) large JO - The electronic journal of combinatorics PY - 2000 VL - 7 UR - http://geodesic.mathdoc.fr/articles/10.37236/1517/ DO - 10.37236/1517 ID - 10_37236_1517 ER -
Charles Knessl; Wojciech Szpankowski. A note on the asymptotic behavior of the heights in \(b\)-trees for \(b\) large. The electronic journal of combinatorics, Tome 7 (2000). doi: 10.37236/1517
Cité par Sources :