A Rappels algorithmiques
425
A.4 Arbres quadrants
Les algorithmes de recherche et d’insertion aux feuilles sur les arbres quadrants de
recherche sont des extensions naturelles des algorithmes correspondants pour les
arbres binaires de recherche, que nous ne détaillons pas davantage.
Comment serait-il possible de généraliser l’algorithme de suppression des arbres
binaires de recherche ? Supprimer une clé dans un nœud interne (et non une feuille)
est compliqué. Concrètement, il est raisonnable de garder toutes les clés ayant
été présentes à un moment dans l’arbre, pour structurer l’ensemble des données,
et d’utiliser un booléen en chaque nœud, marquant si la clé qui s’y trouve a été
supprimée ; lorsque le rapport Nombre de clés effectivement présentes / Nombre de
clés servant à structurer l’espace devient trop faible, l’arbre est reconstruit.
A.5 Tries
Dans cette présentation algorithmique, nous considérons une structure de données
pour le trie avec un alphabet quelconque. Les clés considérées sont des mots
finis. Nous supposons également pour simplifier qu’aucun mot inséré dans le trie
n’est préfixe d’un autre. Cette restriction qui peut paraître artificielle est facile à
garantir par exemple en ajoutant un caractère de terminaison (distinct des lettres de
l’alphabet) à la fin de chacun des mots.
Rappelons aussi que la façon de regarder les clés pour une structure de données
comme le trie est radicalement différente de celle par exemple des arbres binaires
de recherche. Pour un arbre binaire de recherche une clé est « atomique » : elle
est indivisible et la comparaison de deux clés a un coût unitaire. Dans un trie la
clé est non-atomique : elle se décompose comme une séquence de symboles (bits,
caractères, etc.) sur un alphabet.
Nous ne considérons ici que des tries permettant de représenter des dictionnaires.
Dans la pratique les tries sont plutôt utilisés comme tables associatives permettant de
stocker des couples (clé, valeur). Il faudrait modifier les algorithmes en conséquence
pour stocker dans chaque feuille du trie la valeur associée à la clé correspondante
(en plus du suffixe stocké en chaque feuille permettant de reconstituer la clé).
A.5.1 Les types de données
Nous utilisons les types de base chaîne pour les chaînes de caractères, caractère
pour les caractères. La concaténation de chaînes ou de caractères sera notée grâce
à l’opérateur ‘+’. Nous définissons deux fonctions prenant en argument une chaîne
de caractère :
425
A.4 Arbres quadrants
Les algorithmes de recherche et d’insertion aux feuilles sur les arbres quadrants de
recherche sont des extensions naturelles des algorithmes correspondants pour les
arbres binaires de recherche, que nous ne détaillons pas davantage.
Comment serait-il possible de généraliser l’algorithme de suppression des arbres
binaires de recherche ? Supprimer une clé dans un nœud interne (et non une feuille)
est compliqué. Concrètement, il est raisonnable de garder toutes les clés ayant
été présentes à un moment dans l’arbre, pour structurer l’ensemble des données,
et d’utiliser un booléen en chaque nœud, marquant si la clé qui s’y trouve a été
supprimée ; lorsque le rapport Nombre de clés effectivement présentes / Nombre de
clés servant à structurer l’espace devient trop faible, l’arbre est reconstruit.
A.5 Tries
Dans cette présentation algorithmique, nous considérons une structure de données
pour le trie avec un alphabet quelconque. Les clés considérées sont des mots
finis. Nous supposons également pour simplifier qu’aucun mot inséré dans le trie
n’est préfixe d’un autre. Cette restriction qui peut paraître artificielle est facile à
garantir par exemple en ajoutant un caractère de terminaison (distinct des lettres de
l’alphabet) à la fin de chacun des mots.
Rappelons aussi que la façon de regarder les clés pour une structure de données
comme le trie est radicalement différente de celle par exemple des arbres binaires
de recherche. Pour un arbre binaire de recherche une clé est « atomique » : elle
est indivisible et la comparaison de deux clés a un coût unitaire. Dans un trie la
clé est non-atomique : elle se décompose comme une séquence de symboles (bits,
caractères, etc.) sur un alphabet.
Nous ne considérons ici que des tries permettant de représenter des dictionnaires.
Dans la pratique les tries sont plutôt utilisés comme tables associatives permettant de
stocker des couples (clé, valeur). Il faudrait modifier les algorithmes en conséquence
pour stocker dans chaque feuille du trie la valeur associée à la clé correspondante
(en plus du suffixe stocké en chaque feuille permettant de reconstituer la clé).
A.5.1 Les types de données
Nous utilisons les types de base chaîne pour les chaînes de caractères, caractère
pour les caractères. La concaténation de chaînes ou de caractères sera notée grâce
à l’opérateur ‘+’. Nous définissons deux fonctions prenant en argument une chaîne
de caractère :