DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

On the Number of 2-Protected Nodes in Tries and Suffix Trees

Jeffrey Gaither, Yushi Homma, Mark Sellke, Mark Daniel Ward


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

Valid XHTML 1.0 Transitional