On the Stack-Size of General Tries

¹ GREYC, Université de Caen, 14032 Caen, France; (Jeremie.Bourdon@info.unicaen.fr)
² FB Informatik, Johann Wolfgang Goethe-Universität, 60054 Frankfurt a. M., Germany; (nebel@sads.informatik.uni-frankfurt.de)
³ GREYC, Université de Caen, 14032 C aen, France; (Brigitte.Vallee@info.unicaen.fr)

Received: 27 September 2000
Accepted: March 2001

Abstract

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.