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.
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},
year = {2001},
publisher = {EDP-Sciences},
volume = {35},
number = {2},
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/