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 Trees

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

    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.


    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]
    Fundings :
      Source : OpenAIRE Research Graph
    • Emerging Frontiers of Science of Information; Funder: National Science Foundation; Code: 0939370

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 218 times.
    This article's PDF has been downloaded 144 times.