Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-18T05:02:16.497Z Has data issue: false hasContentIssue false

On the Stack-Size of General Tries

Published online by Cambridge University Press:  15 April 2002

Jérémie Bourdon
Affiliation:
GREYC, Université de Caen, 14032 Caen, France; (Jeremie.Bourdon@info.unicaen.fr)
Markus Nebel
Affiliation:
FB Informatik, Johann Wolfgang Goethe-Universität, 60054 Frankfurt a. M., Germany; (nebel@sads.informatik.uni-frankfurt.de)
Brigitte Vallée
Affiliation:
GREYC, Université de Caen, 14032 C aen, France; (Brigitte.Vallee@info.unicaen.fr)
Get access

Abstract

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussedon the average-case analysis ofan important parameter of thistree-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 outunder 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 commonlyused data models (and more), we obtain a precise average-case and probabilistic analysis of stack-size. Furthermore, we studythe dependency between the stack-size and the ordering on symbols inthe alphabet:we establish that, when the source emits independent symbols, theoptimal ordering arises when the most probable symbol is the last one in this order.

Information

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable