Jeffrey Gaither ; Yushi Homma ; Mark Sellke ; Mark Daniel Ward - On the Number of 2-Protected Nodes in Tries and Suffix Trees

dmtcs:3008 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.3008
On the Number of 2-Protected Nodes in Tries and Suffix TreesArticle

Authors: Jeffrey Gaither 1; Yushi Homma 1; Mark Sellke 1; Mark Daniel Ward 2

  • 1 Department of mathematics Purdue University
  • 2 Department of Statistics

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.

https://doi.org/10.46298/dmtcs.3008
Source: HAL:hal-01197232v1
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: 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]
Funding:
    Source : OpenAIRE Graph
  • Emerging Frontiers of Science of Information; Funder: National Science Foundation; Code: 0939370

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 348 times.
This article's PDF has been downloaded 235 times.