30
1 Botanique
plein, et le processus se reproduit récursivement aussi longtemps que nécessaire.
S’il arrive à la racine de l’arbre et que cette racine est pleine, cela entraîne la
création d’une nouvelle racine et l’accroissement de la hauteur de l’arbre.
Ainsi, dans l’arbre de la figure 1.28, insérer 1 ferait intervenir le nœud interne
terminal le plus à gauche, qui contient la seule clé 0, et la modification est donc
limitée à ce nœud ; par contre insérer 13 éclaterait le nœud contenant 15 et 18 et
ferait remonter la médiane de 13, 15 et 18, i.e., 15, dans le nœud parent, qui contient
la seule clé 12 et peut donc accueillir une clé supplémentaire ; il aurait alors trois
enfants. Quant à l’insertion de 50, elle conduirait à remonter jusqu’à la racine de
l’arbre et à l’éclater. Nous ne détaillons pas pour l’instant plus avant ce processus,
qui sera repris dans le chapitre 9 lorsque nous analyserons la frange d’un arbre 2-3.
Cette technique d’insertion est proche de celle des arbres-B et celle-ci sera détaillée
en section 3.2.2.
1.2.7 Arbres digitaux : tries
La structure d’arbre digital la plus simple, également appelée trie, est extrêmement
importante en informatique à la fois du point de vue des structures de données mais
aussi du principe de partitionnement sous-jacent à sa construction. Cette structure
semble avoir été inventée pour la première fois par De La Briandais [53]. Et le terme
« trie » (contraction de tree et retrieval) est dû à Fredkin [109]. Cette structure, de
type dictionnaire, est destinée à représenter un ensemble de clés, chaque clé étant
un mot sur un alphabet.
Nous commençons par définir l’arbre lexicographique associé à un ensemble Y
de mots : il s’agit d’associer un nœud à chaque préfixe apparaissant dans l’ensemble
des préfixes des mots de Y , noté Pref(Y ).
Définition 1.38 Soient Y un ensemble de mots sur un alphabet A et Pref(Y )
l’ensemble des préfixes des mots de Y . Alors l’arbre lexicographique associé à
Y est Pref(Y ).
Remarquons qu’un arbre lexicographique est aussi un arbre préfixe suivant la
définition 1.2 (en changeant d’alphabet).
Exemple 1.39 Sur l’alphabet {a, b}, soit l’ensemble de mots
Y = {aaba, baab, aa, ab}.
L’ensemble des préfixes est
Pref(Y ) = {ε, a, b, aa, ab, ba, aab, baa, aaba, baab}.
1 Botanique
plein, et le processus se reproduit récursivement aussi longtemps que nécessaire.
S’il arrive à la racine de l’arbre et que cette racine est pleine, cela entraîne la
création d’une nouvelle racine et l’accroissement de la hauteur de l’arbre.
Ainsi, dans l’arbre de la figure 1.28, insérer 1 ferait intervenir le nœud interne
terminal le plus à gauche, qui contient la seule clé 0, et la modification est donc
limitée à ce nœud ; par contre insérer 13 éclaterait le nœud contenant 15 et 18 et
ferait remonter la médiane de 13, 15 et 18, i.e., 15, dans le nœud parent, qui contient
la seule clé 12 et peut donc accueillir une clé supplémentaire ; il aurait alors trois
enfants. Quant à l’insertion de 50, elle conduirait à remonter jusqu’à la racine de
l’arbre et à l’éclater. Nous ne détaillons pas pour l’instant plus avant ce processus,
qui sera repris dans le chapitre 9 lorsque nous analyserons la frange d’un arbre 2-3.
Cette technique d’insertion est proche de celle des arbres-B et celle-ci sera détaillée
en section 3.2.2.
1.2.7 Arbres digitaux : tries
La structure d’arbre digital la plus simple, également appelée trie, est extrêmement
importante en informatique à la fois du point de vue des structures de données mais
aussi du principe de partitionnement sous-jacent à sa construction. Cette structure
semble avoir été inventée pour la première fois par De La Briandais [53]. Et le terme
« trie » (contraction de tree et retrieval) est dû à Fredkin [109]. Cette structure, de
type dictionnaire, est destinée à représenter un ensemble de clés, chaque clé étant
un mot sur un alphabet.
Nous commençons par définir l’arbre lexicographique associé à un ensemble Y
de mots : il s’agit d’associer un nœud à chaque préfixe apparaissant dans l’ensemble
des préfixes des mots de Y , noté Pref(Y ).
Définition 1.38 Soient Y un ensemble de mots sur un alphabet A et Pref(Y )
l’ensemble des préfixes des mots de Y . Alors l’arbre lexicographique associé à
Y est Pref(Y ).
Remarquons qu’un arbre lexicographique est aussi un arbre préfixe suivant la
définition 1.2 (en changeant d’alphabet).
Exemple 1.39 Sur l’alphabet {a, b}, soit l’ensemble de mots
Y = {aaba, baab, aa, ab}.
L’ensemble des préfixes est
Pref(Y ) = {ε, a, b, aa, ab, ba, aab, baa, aaba, baab}.