The Variance of the Number of 2-Protected Nodes in a Trie
Jeffrey Gaither, Mark Daniel Ward · 2013
We derive an asymptotic expression for the variance of the number of 2-protected nodes (neither leaves nor parents of leaves) in a binary trie. In an unbiased trie on n leaves we find, for example, that the variance is approximately .934n plus small fluctuations (also of order n); but our result covers the general (biased) case as well. Our proof relies on the asymptotic similarities between a trie and its Poissonized counterpart, whose behavior we glean via the Mellin transform and singularity analysis. Mathematical subject classification: 05C05, 60C05, 68W32, 68W40.