A Rappels algorithmiques
407
Fig. A.5 Insertion de la clé
8 dans l’arbre binaire de
recherche de la figure A.4
A.2.2 Insertion aux feuilles
L’algorithme d’insertion d’une nouvelle clé X dans la feuille adéquate d’un arbre
binaire de recherche A est donné ci-dessous ; c’est la fonction insérerFeuille qui
se contente de trouver la place de cette nouvelle feuille et de la rattacher à l’arbre,
et la création proprement dite de la feuille est le but de la fonction créerFeuille
(figure A.5).
Fonction insérerFeuille(élément X, Arbre A)
// Précondition : A est un arbre binaire de recherche.
// Postcondition : Retourne l’arbre de départ modifié par insertion de X dans
la feuille convenable.
// Utilise : créerFeuille , insérerFeuille
si A == None alors
retourner créerFeuille(X)
sinon
si A.clé ≥ X alors
A.gauche = insérerFeuille(X, A.gauche)
sinon
A.droit = insérerFeuille(X, A.droit)
retourner A
Fonction créerFeuille(élément X)
// Précondition : Aucune
// Postcondition : Retourne un nœud dans lequel la clé X a été insérée.
// Variable locale : Arbre A
// Utilise : nouveau
A = nouveau()
A.clé = X
A.gauche = None
A.droit = None
retourner A