Arbres binaires de recherche

Un arbre binaire de recherche est un arbre binaire (chaque cellule a au plus deux fils). Les éléments sont stockés dans toutes les cellules. Voici une définition possible d'une telle cellule :

(defstruct bincell
  elem
  (left nil)
  (right nil))

Le domaine des éléments doit être totalement ordonné. Pour une cellule $c$ donnée, tous les éléments stockés dans le sous-arbre de gauche sont inférieurs à celui stocké dans $c$ et l'élément stocké dans $c$ est inférieur à tous les éléments stockés dans le sous-arbre droit. Voir la figure 23.8 pour un exemple d'arbre binaire de recherche. Nous allons supposer qu'il n'existe pas de synonymes, à savoir plusieurs éléments avec la même clé. Il n'est donc pas possible d'insérer un élément déjà présent dans l'arbre.

Figure 23.8: Arbre binaire de recherche

La fonction de comparaison de deux éléments du domaine ne peut pas être déterminée automatiquement et doit donc être fournie par l'utilisateur. Elle sera un des arguments de la plupart des fonctions de manipulation de l'arbre.

Les opérations présentées ici renvoient un nouvel arbre dont la structure peut partager une partie de la structure de l'ancien. Il est donc nécessaire de respecter deux règles :

• la valeur de l'opération donne le nouvel arbre ;
• l'ancien arbre a pu être modifié ou pas ; il n'y a aucune garantie qu'il soit intact ou modifié.

Par exemple, si l'arbre qui nous intéresse est la valeur de la variable *tree*, il faut exécuter les opérations de la manière suivante :

(setf *tree* (btree-insert elem *tree*))
(setf *tree* (btree-delete elem *tree*))

Comme avec les fonctions Common Lisp existantes de type find, nos opérations prennent un paramètre mot-clé :key permettant d'appliquer une fonction à un objet avant la comparaison. L'objet fourni à l'opération sera comparé au résultat de cette application.

Les opérations prennent aussi un paramètre mot-clé :test permettant de fournir une fonction arbitraire de test. Cette fonction prend deux paramètres et détermine si le premier est inférieur au deuxième. Le domaine étant totalement ordonné, si pour deux objets $a$ et $b$ on a que $a$ n'est pas inférieur à $b$ et que $b$ n'est pas inférieur à $a$, alors $a$ et $b$ sont égaux.