L'opération d'insertion dans un arbre binaire de recherche doit comparer
l'élément à insérer à tous les éléments d'un chemin partant de la
racine de l'arbre jusqu'à ce qu'un arbre vide soit trouvé. Une
cellule sera alors créée pour remplacer cet arbre vide. Le choix
d'aller à gauche ou à droite est déterminé par la valeur à insérer et
celle du nud. La figure 23.9
montre l'arbre de la figure 23.8 après insertion de l'élément
51.
L'insertion utilise la même convention que la recherche, à savoir qu'il y aura deux valeurs de retour. La première est toujours le nouvel arbre après insertion et la deuxième t ou nil selon si l'objet a été inséré ou pas.
Une autre convention possible est de provoquer une erreur si l'objet existe déjà dans l'arbre.
Voici la fonction d'insertion :
Irene DURAND