On the Stack-Size of General Tries
GREYC, Université de Caen, 14032 Caen, France; (Jeremie.Bourdon@info.unicaen.fr)
2 FB Informatik, Johann Wolfgang Goethe-Universität, 60054 Frankfurt a. M., Germany; (firstname.lastname@example.org)
3 GREYC, Université de Caen, 14032 C aen, France; (Brigitte.Vallee@info.unicaen.fr)
Accepted: March 2001
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.
Mathematics Subject Classification: 68P05 / 68W40 / 94A15
Key words: Average-case analysis of data-structures / information theory / trie / Mellin analysis.
© EDP Sciences, 2001