DOI: 10.1051/ita:2001114


Theoret. Informatics Appl. 35, 163-185 (2001)

On the Stack-Size of General Tries

Jérémie Bourdon¹, Markus Nebel² and Brigitte Vallée<sup>3

1</sup>  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 September 27, 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.

AMS Subject: 68P05, 68W40, 94A15.

Key words: Average-case analysis of data-structures -- information theory -- trie -- Mellin analysis.


© EDP Sciences 2001

What is OpenURL?