[Back]

M. Fuchs, G. Yu, C. Lee:
"On 2-protected nodes in random digital trees.";
Theoretical Computer Science, 622 (2016), 111 - 122.

In this paper, we consider the number of 2-protected nodes in random digital trees. Results for the mean and
variance of this number for tries have been obtained by Gaither, Homma, Sellke and Ward (2012) and Gaither and
Ward (2013) and for the mean in digital search trees by Du and Prodinger (2012). In this short note, we show that
these previous results and extensions such as the variance in digital search trees and limit laws in both cases can be
derived in a systematic way by recent approaches of Fuchs, Hwang and Zacharovas (2010; 2014) and Fuchs and Lee
(2014). Interestingly, the results for the moments we obtain by our approach are quite different from the previous
ones and contain divergent series which have values by appealing to the theory of Abel summability. We also show
that our tools apply to PATRICIA tries, for which the number of 2-protected nodes has not been investigated so far.

Data structures, digital trees, analytic combinatorics, moments, limit theorems, Abel summability