DOAJ Open Access 2012

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

Jeffrey Gaither Yushi Homma Mark Sellke Mark Daniel Ward

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (4)

Jeffrey Gaither

Yushi Homma

Mark Sellke

Mark Daniel Ward

Format Sitasi

APA MLA BibTeX

Gaither, J., Homma, Y., Sellke, M., Ward, M.D. (2012). On the Number of 2-Protected Nodes in Tries and Suffix Trees. https://doi.org/10.46298/dmtcs.3008

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.3008

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.3008
Akses: Open Access ✓