32
1 Botanique
Définition 1.41 Soient un alphabet fini A = {a 1 , . . . , a r } de cardinalité r (avec
r ≥ 1) et Y un ensemble de mots distincts sur l’alphabet A, tel qu’aucun mot ne soit
préfixe d’un autre. Le trie associé à Y est défini récursivement comme suit :
– Si |Y | = 0, le trie est vide : trie(Y ) = ∅.
– Si |Y | = 1, le trie est réduit à une feuille, contenant l’unique élément de Y .
– Si |Y | > 1,
trie(Y ) = (•, trie(Y \a 1 ), . . . , trie(Y \a r )),
où • représente un nœud interne et Y \ a désigne le sous-ensemble construit en
prenant les mots de Y qui commencent par la lettre a mais privés de cette lettre
initiale.
Un trie est donc un arbre dont chaque nœud interne est d’arité au plus r (la taille de
l’alphabet) et marqué par un préfixe d’une clé. Une variante plus légère consiste à
n’indiquer, en chaque nœud interne non racine, ou encore sur le lien avec le parent
de ce nœud, que la dernière lettre du préfixe qui y conduit ; c’est celle que nous
avons retenue pour les figures. Les feuilles, quant à elles, sont marquées par les clés
qu’elles contiennent. La figure 1.32 illustre les deux choix de représentation qui
viennent d’être évoqués (en rapport respectivement avec les définitions 1.40 et 1.41)
pour le même ensemble de mots.
L’avantage du trie est qu’il ne considère que l’ensemble minimal des préfixes
nécessaires pour distinguer les éléments de Y : un trie construit sur un ensemble fini
de clés (qui sont des mots infinis) distincts sera toujours fini.
Remarque 1.42 Seul un mot fini peut être préfixe d’un autre mot (la notion de
préfixe a été définie pour des nœuds dans la définition 1.3 ; elle s’applique bien
évidemment à des mots sur un alphabet). Une manière d’assurer qu’aucune clé n’est
préfixe d’une autre est d’ajouter une lettre spéciale « † » à la fin de chaque mot fini.
Notons qu’un trie construit sur un ensemble Y de n clés a toujours n feuilles, et un
nombre de nœuds internes qui varie en fonction des longueurs des préfixes communs
des clés. Il faudra donc préciser ce qu’on entend par « taille » d’un trie : nombre de
nœuds internes de l’arbre ? nombre de clés ? Dans la suite et puisqu’un trie construit
à partir d’un ensemble de mots de cardinal n possède exactement n feuilles, il est
naturel de considérer pour la taille le nombre de nœuds internes.
Constructions statique ou dynamique
Comme pour la structure d’arbre binaire de recherche, nous pouvons envisager la
structure de trie de deux manières.
(i) Nous avons une construction statique (définition 1.41) où l’ensemble des clés
est disponible avant de construire le trie. Si l’ensemble est un singleton, le trie
est réduit à une feuille. Sinon, la racine du trie est un nœud interne et nous
examinons l’ensemble formé des lettres initiales de chaque clé. Pour chacune
1 Botanique
Définition 1.41 Soient un alphabet fini A = {a 1 , . . . , a r } de cardinalité r (avec
r ≥ 1) et Y un ensemble de mots distincts sur l’alphabet A, tel qu’aucun mot ne soit
préfixe d’un autre. Le trie associé à Y est défini récursivement comme suit :
– Si |Y | = 0, le trie est vide : trie(Y ) = ∅.
– Si |Y | = 1, le trie est réduit à une feuille, contenant l’unique élément de Y .
– Si |Y | > 1,
trie(Y ) = (•, trie(Y \a 1 ), . . . , trie(Y \a r )),
où • représente un nœud interne et Y \ a désigne le sous-ensemble construit en
prenant les mots de Y qui commencent par la lettre a mais privés de cette lettre
initiale.
Un trie est donc un arbre dont chaque nœud interne est d’arité au plus r (la taille de
l’alphabet) et marqué par un préfixe d’une clé. Une variante plus légère consiste à
n’indiquer, en chaque nœud interne non racine, ou encore sur le lien avec le parent
de ce nœud, que la dernière lettre du préfixe qui y conduit ; c’est celle que nous
avons retenue pour les figures. Les feuilles, quant à elles, sont marquées par les clés
qu’elles contiennent. La figure 1.32 illustre les deux choix de représentation qui
viennent d’être évoqués (en rapport respectivement avec les définitions 1.40 et 1.41)
pour le même ensemble de mots.
L’avantage du trie est qu’il ne considère que l’ensemble minimal des préfixes
nécessaires pour distinguer les éléments de Y : un trie construit sur un ensemble fini
de clés (qui sont des mots infinis) distincts sera toujours fini.
Remarque 1.42 Seul un mot fini peut être préfixe d’un autre mot (la notion de
préfixe a été définie pour des nœuds dans la définition 1.3 ; elle s’applique bien
évidemment à des mots sur un alphabet). Une manière d’assurer qu’aucune clé n’est
préfixe d’une autre est d’ajouter une lettre spéciale « † » à la fin de chaque mot fini.
Notons qu’un trie construit sur un ensemble Y de n clés a toujours n feuilles, et un
nombre de nœuds internes qui varie en fonction des longueurs des préfixes communs
des clés. Il faudra donc préciser ce qu’on entend par « taille » d’un trie : nombre de
nœuds internes de l’arbre ? nombre de clés ? Dans la suite et puisqu’un trie construit
à partir d’un ensemble de mots de cardinal n possède exactement n feuilles, il est
naturel de considérer pour la taille le nombre de nœuds internes.
Constructions statique ou dynamique
Comme pour la structure d’arbre binaire de recherche, nous pouvons envisager la
structure de trie de deux manières.
(i) Nous avons une construction statique (définition 1.41) où l’ensemble des clés
est disponible avant de construire le trie. Si l’ensemble est un singleton, le trie
est réduit à une feuille. Sinon, la racine du trie est un nœud interne et nous
examinons l’ensemble formé des lettres initiales de chaque clé. Pour chacune