A Note on the Asymptotic Behavior of the Heights in $b$-Tries for $b$ Large

摘要: We study the limiting distribution of height in a generalized trie which external nodes are capable to store up $b$ items (the so called $b$-tries). assume that such tree is built from $n$ random strings (items) generated by an unbiased memoryless source. In this paper, we discuss case when and both large. shall identify five regions should be compared three obtained for fixed $b$. prove most $n$, concentrated at single point $k_1=\lfloor \log_2 (n/b)\rfloor +1$ as $n,b\to \infty$. observe quite different than $b$, extreme value type around $(1+1/b)\log_2 n$. derive our results analytic methods, namely generating functions saddle method. also present some numerical verification results.