428
A Rappels algorithmiques
Ces procédures sont utiles pour décrire l’algorithme de suppression d’un mot dans
un trie. Nous donnons ici leur description en pseudo-code.
Fonction étendre(Noeud N)
// Précondition : N est un nœud et si il est externe la chaîne associée est non
vide.
// Postcondition : N est un nœud, modifié seulement si N était un nœud
externe.
// Variables locales : chaîne t ; caractère lettre
// Utilise : estExterne, premièreLettre, finChaîne, nouveauNoeud
si estExterne(N) alors
t = N.texte
lettre = premièreLettre(t)
N.enfant[lettre] = nouveauNoeud(finChaîne(t))
// On a créé une feuille, enfant de N
N.texte = ""
// Le nœud N est devenu interne car il a maintenant un descendant
retourner N
Procédure contracter(Noeud N)
// Précondition : N est un nœud.
// Postcondition : N est un nœud modifié si N était un nœud unaire avec
comme unique fille une feuille.
// Variables locales : caractère c, Noeud q
// Utilise : estUnaire, estExterne, premierEnfant
si estUnaire(N) alors
(c, q) = premierEnfant(N)
q = N.enfant[c]
si estExterne(q) alors
N.texte = c + q.texte
// concatène la lettre avec le texte de la feuille
del N.Enfant[c]
// supprime le fils par la lettre c de l’ensemble des descendants du
nœud
retourner N