Recherche

Nous allons nous inspirer des tables de hachage de Common Lisp, en définissant une fonction de recherche qui renvoie deux valeurs. La première sera l'objet trouvé (ou nil si l'objet n'existe pas) et la deuxième sera t ou nil selon l'existence ou non de l'objet. Ceci est nécessaire car il est impossible de déterminer d'après la première valeur uniquement si l'objet n'existe pas ou si l'objet nil a été trouvé. Une application dont le domaine ne contient pas nil peut se contenter de la première valeur.

Voici la fonction de recherche :

(defun btree-find (elem tree &key (test #'<) (key #'identity))
  (cond ((null tree) (values nil nil))
        ((funcall test
                  elem
                  (funcall key (bincell-elem tree)))
         (btree-find elem (bincell-left tree)
                     :test test :key key))
        ((funcall test
                  (funcall key (bincell-elem tree))
                  elem)
         (btree-find elem (bincell-right tree)
                     :test test :key key))
        (t (values (bincell-elem tree) t))))