Insertion

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.

Figure 23.9: Insertion dans un arbre binaire de recherche

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 :

(defun btree-insert (elem tree &key (test #'<) (key #'identity))
    (cond ((null tree) (values (make-bincell :elem elem) t))
          ((funcall test
                    elem
                    (funcall key (bincell-elem tree)))
           (multiple-value-bind (ltree inserted)
               (btree-insert elem (bincell-left tree)
                             :test test :key key)
             (setf (bincell-left tree) ltree)
             (values tree inserted)))
          ((funcall test
                    (funcall key (bincell-elem tree))
                    elem)
           (multiple-value-bind (rtree inserted)
               (btree-insert elem (bincell-right tree)
                             :test test :key key)
             (setf (bincell-right tree) rtree)
             (values tree inserted)))
          (t (values tree nil))))