On the Number of 2-Protected Nodes in Tries and Suffix Trees
Jeffrey Gaither, Yushi Homma, Mark Sellke, Mark Daniel Ward
Abstract
We use probabilistic and combinatorial tools on strings to discover the average number of 2-protected nodes in tries and in suffix trees. Our analysis covers both the uniform and non-uniform cases. For instance, in a uniform trie with n leaves, the number of 2-protected nodes is approximately 0.803n, plus small first-order fluctuations. The 2-protected nodes are an emerging way to distinguish the interior of a tree from the fringe.
Full Text: PostScript PDF