The trie, or digital tree, is a standard data structure for representing sets of strings over a given finite alphabet. Since Knuth's original work (1973), these data structures have been extensively studied and analyzed. In this paper, we present an algebraic approach to the analysis of average storage and average time required by the retrieval algorithms of trie structures under the prefix model. This approach extends the work of Flajolet et al. for other models which, unlike the prefix model, assume that no key in a sample set is the prefix of another. As the main application, we analyze the average running time of two algorithms for computing set intersections.
R~um~
Le trie, ou trie num&ique, est une structure de donnres standard pour reprrsenter des ensembles de mots sur un alphabet fini donnr. Depuis le travail original de , ces structures de donnres ont 6t6 intensivement 6tudires et analysres. Dans cet article, nous prrsentons une approche algrbrique de l'analyse de l'espace moyen et du temps moyen requis par les algorithmes de recherche dans les structures de trie utilisant le modOle prOfixe. Cette approche 6tend le travail de Flajolet et al. /t d'autres modrles, qui, contrairement au modble prrfixe, supposent qu'aucune clef dans un 6chantillon n'est le prrfixe d'une autre. Comme principale application, nous analysons le temps d'rxrution moyen de deux algorithmes pour le calcul d'intersections d'ensembles.