432
A Rappels algorithmiques
Procédure supprimer(Trie T, chaîne s)
// Précondition : T est une structure de type Trie, s est une chaîne de
caractères.
// Postcondition : la clé s, si présente initialement dans le trie, est supprimée.
// Utilise : supprimerNoeud
si T.racine != None alors
Trie.racine = supprimerNoeud(T.racine, s)
La fonction récursive suivante utilise la fonction contracter vue précédemment
et qui est appelée sur une structure de type Noeud (racine du sous-trie courant).
Comme le sous-trie est susceptible d’être complètement modifié, la fonction renvoie
soit None (si le nœud n’existe plus) soit le nœud du sous-trie initialement considéré
après modification.
Fonction supprimerNoeud(Noeud N, chaîne s)
// Précondition : N est un nœud d’un trie, s est une chaîne de caractères.
// Postcondition : la chaîne s, si présente initialement dans le sous-trie de
racine N, est supprimée. La fonction renvoie la racine du sous-trie modifié,
ou None si le sous-trie n’existe plus.
// Variables locales : caractère c ; Noeud Q ; chaîne next
// Utilise : estExterne, premièreLettre, finChaîne, contracter,
supprimerNoeud
si estExterne(N) alors
si N.texte == s alors
retourner None
//suffixe trouvé, on supprime le nœud
sinon
retourner N
//suffixe non trouvé
// Ici le nœud N est supposé interne
c = premièreLettre(s)
next = finChaîne(s)
si c dans N.enfant alors
Q = supprimerNoeud(N.enfant[c], next)
si Q == None alors
del N.enfant[c]
sinon
N.enfant[c] = Q
N = contracter(N)
// Éventuellement contracter si le nœud est devenu unaire
retourner N