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 TreesConference paper

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: [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], [en] retrieval trees, suffix trees, Poissonization, Mellin transforms, pattern matching
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 486 times.
This article's PDF has been downloaded 363 times.