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

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

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.80...

Full description

Bibliographic Details
Main Authors: Jeffrey Gaither, Yushi Homma, Mark Sellke, Mark Daniel Ward
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2012-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
retrieval trees
suffix trees
poissonization
mellin transforms
pattern matching
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Online Access:https://dmtcs.episciences.org/3008/pdf

Internet

https://dmtcs.episciences.org/3008/pdf

Similar Items