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

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

Valid XHTML 1.0 Transitional