Tries and PATRICIA tries are fundamental data structures in computer science with numerous applications. In a recent paper, a general framework for obtaining the mean and variance of additive shape parameters of tries and PATRICIA tries under the Bernoulli model was proposed. In this note, we show that a slight modification of this framework yields a central limit theorem for shape parameters, too. This central limit theorem contains many of the previous central limit theorems from the literature and it can be used to prove recent conjectures and derive new results. As an example, we will consider a refinement of the size of tries and PATRICIA tries, namely, the number of nodes of fixed outdegree and obtain (univariate and bivariate) central limit theorems. Moreover, trivariate central limit theorems for size, internal path length and internal Wiener index of tries and PATRICIA tries are derived as well.
@article{10_37236_3763,
author = {Michael Fuchs and Chung-Kuei Lee},
title = {A general central limit theorem for shape parameters of \(m\)-ary tries and {PATRICIA} tries},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3763},
zbl = {1300.68021},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3763/}
}
TY - JOUR
AU - Michael Fuchs
AU - Chung-Kuei Lee
TI - A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3763/
DO - 10.37236/3763
ID - 10_37236_3763
ER -
%0 Journal Article
%A Michael Fuchs
%A Chung-Kuei Lee
%T A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3763/
%R 10.37236/3763
%F 10_37236_3763
Michael Fuchs; Chung-Kuei Lee. A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3763
