34
1 Botanique
– si le trie n’est pas une feuille, pour une clé x = aw de première lettre a, nous
insérons récursivement w dans le sous-arbre correspondant à la lettre a.
Après n insertions, nous avons donc un trie de n feuilles.
Remarque 1.43 Contrairement aux arbres binaires de recherche, un trie construit
sur un ensemble donné de mots ne dépend que de cet ensemble, et non de l’ordre
dans lequel on insère les mots. L’exercice 7.3 précisera le coût de la construction
dynamique en fonction de paramètres usuels de trie.
1.2.8 Autres types d’arbres digitaux
Trie paginé La première généralisation concerne le trie paginé (« bucket trie »
en anglais), encore appelé b-trie. C’est une structure de trie dont la règle récursive
d’arrêt lors de la construction est légèrement modifiée.
Définition 1.44 (Trie paginé) Soit r un entier strictement positif, A =
{a 1 , . . . , a r } un alphabet de cardinal r et b ≥ 1 un entier appelé capacité. On
définit le b-trie associé à un ensemble Y (noté bucket(Y )) de mots distincts sur A
tels qu’aucun mot ne soit préfixe d’un autre grâce aux règles récursives suivantes :
– si |Y | = 0, alors bucket(Y ) est vide.
– si |Y | ≤ b, alors bucket(Y ) est une feuille marquée par Y .
– si |Y | > b, bucket(Y ) est
bucket(Y ) = (•, bucket(Y \ a 1 ), . . . , bucket(Y \ a r )) ,
où le symbole • désigne un nœud interne et où Y \ a désigne le sous-ensemble
de Y contenant les mots qui commencent par a et dont on a retiré cette première
lettre a.
Nous voyons immédiatement que le trie usuel correspond au cas b = 1. La quantité
b est appelée capacité, car d’un point de vue informatique les feuilles sont vues
comme des pages ayant la capacité de stocker jusqu’à b données. Un exemple de
b-trie avec b = 2 est représenté à la figure 1.33.
Arbre PATRICIA L’arbre PATRICIA (acronyme de Practical Algorithm To
Retrieve Information Coded In Alphanumeric) a été introduit par Morrison en
1968 [190]. L’idée est de contracter les branches du trie en ne gardant que les nœuds
internes avec au moins deux fils. En effet les nœuds internes sans branchement
correspondent à des préfixes qui ne permettent pas de départager deux mots. Les
arêtes de l’arbre ne sont donc plus marquées par des lettres mais par des mots. Un
exemple est donné en figure 1.34.
Arbre digital de recherche L’arbre digital de recherche allie le principe de
construction d’un arbre binaire de recherche (un nœud interne contient une clé) à
celui d’un trie (les lettres composant la clé guident la recherche). Cette structure
1 Botanique
– si le trie n’est pas une feuille, pour une clé x = aw de première lettre a, nous
insérons récursivement w dans le sous-arbre correspondant à la lettre a.
Après n insertions, nous avons donc un trie de n feuilles.
Remarque 1.43 Contrairement aux arbres binaires de recherche, un trie construit
sur un ensemble donné de mots ne dépend que de cet ensemble, et non de l’ordre
dans lequel on insère les mots. L’exercice 7.3 précisera le coût de la construction
dynamique en fonction de paramètres usuels de trie.
1.2.8 Autres types d’arbres digitaux
Trie paginé La première généralisation concerne le trie paginé (« bucket trie »
en anglais), encore appelé b-trie. C’est une structure de trie dont la règle récursive
d’arrêt lors de la construction est légèrement modifiée.
Définition 1.44 (Trie paginé) Soit r un entier strictement positif, A =
{a 1 , . . . , a r } un alphabet de cardinal r et b ≥ 1 un entier appelé capacité. On
définit le b-trie associé à un ensemble Y (noté bucket(Y )) de mots distincts sur A
tels qu’aucun mot ne soit préfixe d’un autre grâce aux règles récursives suivantes :
– si |Y | = 0, alors bucket(Y ) est vide.
– si |Y | ≤ b, alors bucket(Y ) est une feuille marquée par Y .
– si |Y | > b, bucket(Y ) est
bucket(Y ) = (•, bucket(Y \ a 1 ), . . . , bucket(Y \ a r )) ,
où le symbole • désigne un nœud interne et où Y \ a désigne le sous-ensemble
de Y contenant les mots qui commencent par a et dont on a retiré cette première
lettre a.
Nous voyons immédiatement que le trie usuel correspond au cas b = 1. La quantité
b est appelée capacité, car d’un point de vue informatique les feuilles sont vues
comme des pages ayant la capacité de stocker jusqu’à b données. Un exemple de
b-trie avec b = 2 est représenté à la figure 1.33.
Arbre PATRICIA L’arbre PATRICIA (acronyme de Practical Algorithm To
Retrieve Information Coded In Alphanumeric) a été introduit par Morrison en
1968 [190]. L’idée est de contracter les branches du trie en ne gardant que les nœuds
internes avec au moins deux fils. En effet les nœuds internes sans branchement
correspondent à des préfixes qui ne permettent pas de départager deux mots. Les
arêtes de l’arbre ne sont donc plus marquées par des lettres mais par des mots. Un
exemple est donné en figure 1.34.
Arbre digital de recherche L’arbre digital de recherche allie le principe de
construction d’un arbre binaire de recherche (un nœud interne contient une clé) à
celui d’un trie (les lettres composant la clé guident la recherche). Cette structure