A Rappels algorithmiques
427
Fig. A.23 Illustration pour la fonction étendre qui transforme une feuille (contenant le mot av)
en un nœud interne unaire ayant par la lettre a une feuille pour unique fils (contenant v), et la
fonction contracter qui effectue l’opération inverse. Une feuille est représentée par un cadre
contenant le suffixe lui correspondant. Les flèches pointillées à partir de N pointent sur le nœud
passé en argument à la fonction
Nous utilisons plusieurs fonctions qui permettent d’accéder à diverses informations sur un nœud :
– La fonction estExterne(Noeud N) renvoie Vrai si le nœud N est un nœud
externe (sans fils) et Faux sinon ;
– La fonction estUnaire(Noeud N) renvoie Vrai si le nœud N n’a qu’un seul
nœud fils et Faux sinon ;
– La fonction premierEnfant(Noeud N) pour un nœud interne N renvoie le
couple (caractère c, Noeud P) où c est le plus petit symbole pour l’ordre
lexicographique présent sur les liens descendant du nœud N. Le nœud P est le fils
descendant de N par cette lettre c.
Enfin, dans la suite nous utiliserons deux fonctions auxiliaires, inverses l’une
de l’autre, qui rallongent ou raccourcissent une branche, et illustrées dans la
figure A.23 :
– La fonction étendre(Noeud N) prend en argument un nœud et dans le cas où
il est un nœud externe associé à un mot non vide 2 w = av (avec a une lettre et v
le suffixe de w) modifie la feuille pour en faire un nœud interne avec comme fille
par la lettre a une feuille contenant v. Le nœud interne créé est donc unaire. Ce
nœud est aussi le résultat de la fonction. Si le nœud n’est pas une feuille, cette
fonction renvoie le nœud non modifié.
– La fonction contracter(Noeud N) prend un argument un nœud. Dans le cas
où le nœud est unaire et de plus a pour descendant, par une certaine lettre a,
une feuille contenant un mot v, cette fonction modifie le nœud pour en faire une
feuille contenant le mot w = av. Si le nœud n’est pas unaire, cette fonction
renvoie le nœud non modifié.
2 Le mot ne peut être vide car sinon il est impossible de développer la branche.
427
Fig. A.23 Illustration pour la fonction étendre qui transforme une feuille (contenant le mot av)
en un nœud interne unaire ayant par la lettre a une feuille pour unique fils (contenant v), et la
fonction contracter qui effectue l’opération inverse. Une feuille est représentée par un cadre
contenant le suffixe lui correspondant. Les flèches pointillées à partir de N pointent sur le nœud
passé en argument à la fonction
Nous utilisons plusieurs fonctions qui permettent d’accéder à diverses informations sur un nœud :
– La fonction estExterne(Noeud N) renvoie Vrai si le nœud N est un nœud
externe (sans fils) et Faux sinon ;
– La fonction estUnaire(Noeud N) renvoie Vrai si le nœud N n’a qu’un seul
nœud fils et Faux sinon ;
– La fonction premierEnfant(Noeud N) pour un nœud interne N renvoie le
couple (caractère c, Noeud P) où c est le plus petit symbole pour l’ordre
lexicographique présent sur les liens descendant du nœud N. Le nœud P est le fils
descendant de N par cette lettre c.
Enfin, dans la suite nous utiliserons deux fonctions auxiliaires, inverses l’une
de l’autre, qui rallongent ou raccourcissent une branche, et illustrées dans la
figure A.23 :
– La fonction étendre(Noeud N) prend en argument un nœud et dans le cas où
il est un nœud externe associé à un mot non vide 2 w = av (avec a une lettre et v
le suffixe de w) modifie la feuille pour en faire un nœud interne avec comme fille
par la lettre a une feuille contenant v. Le nœud interne créé est donc unaire. Ce
nœud est aussi le résultat de la fonction. Si le nœud n’est pas une feuille, cette
fonction renvoie le nœud non modifié.
– La fonction contracter(Noeud N) prend un argument un nœud. Dans le cas
où le nœud est unaire et de plus a pour descendant, par une certaine lettre a,
une feuille contenant un mot v, cette fonction modifie le nœud pour en faire une
feuille contenant le mot w = av. Si le nœud n’est pas unaire, cette fonction
renvoie le nœud non modifié.
2 Le mot ne peut être vide car sinon il est impossible de développer la branche.