The stack-size of tries: A combinatorial study (Q5958316): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4101884 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5659554 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Singularity Analysis of Generating Functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The average height of r-tuply rooted planted plane trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3779735 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5585020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4004056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992743 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 23:22, 3 June 2024
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