On the Number of 2-Protected Nodes in Tries and Suffix Trees
Jeffrey Gaither (1) (2), Yushi Homma (1) (2), Mark Sellke (1) (2), Mark Daniel Ward (3) (4)
(1) Department of mathematics Purdue University
(2) Department of Mathematics [West Lafayette]
(3) Department of Statistics
(4) Department of Statistics [West Lafayette]
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.803$n$, plus small first-order fluctuations. The 2-protected nodes are an emerging way to distinguish the interior of a tree from the fringe.
Keywords
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
