Geodesic
On the stack-size of general tries
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 163-185

Voir la notice de l'article provenant de la source Numdam

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions that encompass all commonly used data models (and more), we obtain a precise average-case and probabilistic analysis of stack-size. Furthermore, we study the dependency between the stack-size and the ordering on symbols in the alphabet: we establish that, when the source emits independent symbols, the optimal ordering arises when the most probable symbol is the last one in this order.

Classification : 68P05, 68W40, 94A15
Keywords: average-case analysis of data-structures, information theory, trie, Mellin analysis 
@article{ITA_2001__35_2_163_0,
     author = {Bourdon, J\'er\'emie and Nebel, Markus and Vall\'ee, Brigitte},
     title = {On the stack-size of general tries},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {163--185},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1862461},
     zbl = {1016.68064},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_2_163_0/}
}
TY  - JOUR
AU  - Bourdon, Jérémie
AU  - Nebel, Markus
AU  - Vallée, Brigitte
TI  - On the stack-size of general tries
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 163
EP  - 185
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_2_163_0/
LA  - en
ID  - ITA_2001__35_2_163_0
ER  - 
%0 Journal Article
%A Bourdon, Jérémie
%A Nebel, Markus
%A Vallée, Brigitte
%T On the stack-size of general tries
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 163-185
%V 35
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_2_163_0/
%G en
%F ITA_2001__35_2_163_0
Bourdon, Jérémie; Nebel, Markus; Vallée, Brigitte. On the stack-size of general tries. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 163-185. http://geodesic.mathdoc.fr/item/ITA_2001__35_2_163_0/