The stack-size of tries: A combinatorial study

DOI10.1016/S0304-3975(00)00416-3MaRDI QIDQ5958316zbMATH OpenFDO

Authors Markus E. Nebel

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00416-3

zbMATH Keywords

average case analysiscombinatorial structuresstack-sizetries

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Review text

In this paper, we introduce a class of extended binary trees that resembles all possible tree-structures of binary tries. Assuming a uniform distribution of those trees we prove that for \(\alpha\) being the number of internal nodes the average stack-size is given by \(\frac 32\pi \alpha\). Since this result is quite similar to that for ordinary extended binary trees an attempt to find an explanation for that similarity using a quantitative level is made.

Recommendations

• The stack-size of combinatorial tries revisited
• On the stack-size of general tries
• A probabilistic analysis of the height of tries and of the complexity of triesort
• scientific article; zbMATH DE number 1156488
• Trie size in a dynamic list structure

Cites work

• scientific article; zbMATH DE number 4041254 (Why is no real title available?)
• scientific article; zbMATH DE number 43081 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3390782 (Why is no real title available?)
• Singularity Analysis of Generating Functions
• The average height of r-tuply rooted planted plane trees

Cited in

(5)

• Maximum likelihood analysis of algorithms and data structures
• A one-to-one correspondence between two classes of ordered trees
• The stack-size of combinatorial tries revisited
• On the stack-size of general tries
• scientific article; zbMATH DE number 1156488 (Why is no real title available?)

This page was built for publication: The stack-size of tries: A combinatorial study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958316)