A Rappels algorithmiques
429
A.5.2 Insertion
Comme souvent pour les tries, un algorithme est décomposé en deux parties : une
procédure ou fonction correspond à la structure haut niveau du trie, et une procédure
(ou fonction auxiliaire) agit récursivement sur la structure de données.
La procédure suivante ajoute un mot à un trie pour la structure de type Trie, et
sert essentiellement à traiter le cas particulier du trie vide.
Procédure insérer(Trie T, chaîne s)
// Précondition : T est une structure de type Trie, s est une chaîne de
caractères.
// Postcondition : la chaîne s a été ajoutée au trie T.
// Utilise : insérerNoeud, nouveauNoeud
si T.racine == None alors
T.racine = nouveauNoeud(s) // On crée une feuille
sinon
insérerNoeud(T.racine, s) //appel sur la racine
La procédure auxiliaire suivante est récursive et insère une chaîne de caractères
s à partir du nœud N (vu comme la racine d’un sous-trie non vide).
Procédure insérerNoeud(Noeud N, chaîne s)
// Précondition : N est nœud d’un trie, s est une chaîne de caractères.
// Postcondition : N est un nœud d’un trie.
// Variables locales : caractère c, chaîne next
// Utilise : étendre, premièreLettre, finChaîne, insérerNoeud,
nouveauNoeud
si estExterne(N) alors
si s == N.texte alors
retourner // Mot déjà présent dans le trie
sinon
étendre(N) // N est une feuille, on étend
c = premièreLettre(s)
next = finChaîne(s)
si c dans N.enfant alors
insérerNoeud(N.enfant[c], next)
sinon
N.enfant[c] = nouveauNoeud(next) // On crée une feuille