1.2 Arbres marqués
35
Fig. 1.33 Représentation d’un b-trie pour une capacité b = 2 pour l’ensemble de mots
{aabbaa, aabcb, bcaac, bcacab, caaba, caba, cacbbb} de la figure 1.32. Un symbole de terminaison † est ajouté à la fin de chaque mot (à titre d’illustration puisque sur cet exemple aucun
mot n’est préfixe d’un autre, et le symbole de terminaison est inutile)
Fig. 1.34 Un trie PATRICIA pour l’ensemble de mots de la figure 1.32. Un symbole de terminaison
† est ajouté à la fin de chaque mot
se distingue du trie car elle stocke un mot en chaque nœud. Dans la littérature,
l’arbre digital de recherche est le plus souvent un arbre binaire (cf. Knuth[156] ou
Sedgewick[231]) mais il semble que cela soit surtout pour des facilités d’exposition.
Nous pouvons évidemment généraliser au cas d’un alphabet non binaire (ce qui est
fait dans la suite).
Définition 1.45 (Arbre digital de recherche) Les arbres digitaux de recherche
sont construits sur un n-uplet S = (s 1 , . . . , s n ) de mots distincts sur l’alphabet A.
L’arbre digital de recherche dst(S) est défini récursivement par :
– Si |S| = 0 alors l’arbre digital de recherche est dst(S) = ∅.
– Si |S| > 0, l’arbre digital dst(S) de recherche est
dst(S) = (s 1 , dst(
•
S \ a 1 ), . . . , dst(
•
S \ a r )),
où pour S = (s 1 , . . . , s n ) la notation
•
S désigne (s 2 , . . . , s n ) (la suite privée de
son premier élément) et S \ a désigne la suite construite en prenant les mots de
S qui commencent par la lettre a mais privés de cette lettre initiale.
35
Fig. 1.33 Représentation d’un b-trie pour une capacité b = 2 pour l’ensemble de mots
{aabbaa, aabcb, bcaac, bcacab, caaba, caba, cacbbb} de la figure 1.32. Un symbole de terminaison † est ajouté à la fin de chaque mot (à titre d’illustration puisque sur cet exemple aucun
mot n’est préfixe d’un autre, et le symbole de terminaison est inutile)
Fig. 1.34 Un trie PATRICIA pour l’ensemble de mots de la figure 1.32. Un symbole de terminaison
† est ajouté à la fin de chaque mot
se distingue du trie car elle stocke un mot en chaque nœud. Dans la littérature,
l’arbre digital de recherche est le plus souvent un arbre binaire (cf. Knuth[156] ou
Sedgewick[231]) mais il semble que cela soit surtout pour des facilités d’exposition.
Nous pouvons évidemment généraliser au cas d’un alphabet non binaire (ce qui est
fait dans la suite).
Définition 1.45 (Arbre digital de recherche) Les arbres digitaux de recherche
sont construits sur un n-uplet S = (s 1 , . . . , s n ) de mots distincts sur l’alphabet A.
L’arbre digital de recherche dst(S) est défini récursivement par :
– Si |S| = 0 alors l’arbre digital de recherche est dst(S) = ∅.
– Si |S| > 0, l’arbre digital dst(S) de recherche est
dst(S) = (s 1 , dst(
•
S \ a 1 ), . . . , dst(
•
S \ a r )),
où pour S = (s 1 , . . . , s n ) la notation
•
S désigne (s 2 , . . . , s n ) (la suite privée de
son premier élément) et S \ a désigne la suite construite en prenant les mots de
S qui commencent par la lettre a mais privés de cette lettre initiale.