The stack-size of tries: A combinatorial study (Q5958316)
From MaRDI portal
scientific article; zbMATH DE number 1715317
Language | Label | Description | Also known as |
---|---|---|---|
English | The stack-size of tries: A combinatorial study |
scientific article; zbMATH DE number 1715317 |
Statements
The stack-size of tries: A combinatorial study (English)
0 references
3 March 2002
0 references
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.
0 references
average case analysis
0 references
combinatorial structures
0 references
stack-size
0 references
tries
0 references