Arbre binaire de recherche

Définition

Un arbre binaire de recherche est un arbre de recherche où chaque sommet a au plus deux fils et dans lequel les informations sont stockées dans chaque sommet de l'arbre.

Le domaine des données stockées dans un tel arbre doit être ordonné.

Représentation

Afin de représenter un arbre binaire de recherche, nous allons considérer qu'un arbre vide (contenant aucun élément) est représenté par la valeur NIL. Un arbre contenant au moins un élément est représenté par un sommet avec les opérations suivantes :

créer-sommet(données, gauche, droite)
données(sommet)
gauche(sommet)
droite(sommet)

L'opération créer-sommetrenvoie un nouveau sommet à partir d'une donnée (un objet à stocker), un sous arbre gauche et un sous arbre droite. Les trois opérations suivantes permettent de récupérer l'objet stocké, le sous arbre gauche et le sous arbre droite d'un sommet respectivement. Ces trois opérations sont également utilisable pour modifier ces trois composants d'un sommet, au quel cas elle figureront à gauche d'un affectation.

Opérations de base

L'opération principale d'un arbre binaire de recherche est la recherche d'un objet stocké dans l'arbre à partir d'une clé. Les objets stockés peuvent être arbitrairement complexes, comme des personnes, des voitures, etc. La clé est un objet relativement simple qui permet d'identifier de manière unique un objet, comme le numéro de sécurité sociale ou le numéro d'immatriculation.

Afin de trouver un objet stocké dans l'arbre à partir d'une clé, il faut pouvoir :

Les deux fonctions ci-dessus ne peuvent pas être déterminées à partir du type des objets stockés dans l'arbre, car il est entièrement possible d'envisager une application contenant plusieurs arbres binaires de recherche différents, contenant le même type de données (des personnes par exemple) avec deux clés différentes (numéro de sécurité sociale, le nom, le numéro de téléphone, le numéro de carte bancaire, etc). La seule solution est donc de passer ces fonctions comme arguments à nos opérations.

Par la suite, nous supposons que le domaine est totalement ordonné, à savoir si ni x inférieur à y, ni y inférieur à x, alors x est égal à y. Nous supposons également que une clé est unique, à savoir qu'il n'est pas possible de stocker deux objets différents dans l'arbre avec une seule clé.

Recherche d'un objet à partir d'une clé

Voici une première version de l'opération de recherche :

objet
chercher(objet clé, arbre a, fonction clé-fonc, fonction <)
  si a = nil
  alors renvoyer nil
  sinon si <(clé, clé-fonc(données(a)))
  alors renvoyer chercher(clé, gauche(a), clé-fonc, <)
  sinon si <(clé-fonc(données(a)),clé)
  alors renvoyer chercher(clé, droite(a), clé-fonc, <)
  sinon renvoyer données(a)

Cette version ne permet pas à l'objet NIL d'être stocké dans l'arbre, ce qui peut être nécessaire parfois. Un façon de corriger ce problème est de trouver un autre mécanisme (autre que de renvoyer une valeur) pour indiquer que l'objet n'existe pas. Un tel mécanisme possible est de lever une exception (indiqué par un appel à assert dans notre exemple) :

objet
chercher(objet clé, arbre a, fonction clé-fonc, fonction <)
  assert(a != nil)	       
  si <(clé, clé-fonc(données(a)))
  alors renvoyer chercher(clé, gauche(a), clé-fonc, <)
  sinon si <(clé-fonc(données(a)),clé)
  alors renvoyer chercher(clé, droite(a), clé-fonc, <)
  sinon renvoyer données(a)

Le mécanisme des exceptions est pourtant assez lourd, à la fois concernant le coût (au niveau performance) et la quantité de code nécessaire pour traiter l'exception, surtout qu'il est relativement rare de vouloir stocker NIL. Une autre façon est de renvoyer deux valeur : la première valeur est comme avant, à savoir l'objet stocké (ou NIL si l'objet n'est pas dans l'arbre), et la deuxième valeur est un booléen indiquant si la première valeur représente un objet trouvé ou le fait qu'aucun objet avec cette clé n'existe :

objet, booléen 
chercher(objet clé, arbre a, fonction clé-fonc, fonction <)
  si a = nil
  alors renvoyer nil, faux
  sinon si <(clé, clé-fonc(données(a)))
  alors renvoyer chercher(clé, gauche(a), clé-fonc, <)
  sinon si <(clé-fonc(données(a)),clé)
  alors renvoyer chercher(clé, droite(a), clé-fonc, <)
  sinon renvoyer données(a), vrai

Dans certains langages de programmation (comme Common Lisp), il est déjà possible de renvoyer plusieurs valeurs, ce qui rend ce mécanisme très pratique. Dans certains autres langages, c'est plus difficile. En C par exemple, on peut soit renvoyer une structure, soit renvoyer l'une des valeur avec le mécanisme normal et l'autre en passant un pointeur sur une variable.

Une troisième possibilité est de demander au client de passer un argument contenant une valeur dont il est sûr ne figure pas dans l'arbre. Par exemple, si l'arbre contient des personnes, alors, on lui demande de créer une personne fictive qui ne sera jamais stocké dans l'arbre. C'est cette valeur qui sera renvoyée lorsque l'objet n'est pas trouvé :

objet
chercher(objet clé, arbre a, fonction clé-fonc, fonction <, objet bidon)
  si a = nil
  alors renvoyer bidon
  sinon si <(clé, clé-fonc(données(a)))
  alors renvoyer chercher(clé, gauche(a), clé-fonc, <, bidon)
  sinon si <(clé-fonc(données(a)),clé)
  alors renvoyer chercher(clé, droite(a), clé-fonc, <, bidon)
  sinon renvoyer données(a)

Insertion d'un objet

Voici la première version de l'opération d'insertion d'un objet dans l'arbre. Le client n'a pas besoin de passer la clé, car celle-ci est calculable à partir de l'objet grâce à fonction prévue à cet effet :

arbre
insérer(objet obj, arbre a, fonction clé-fonc, fonction <)
  si a = nil
  alors renvoyer créer-sommet(obj, nil, nil)
  sinon si <(clé-fonc(obj), clé-fonc(données(a)))
  alors 
    gauche(a) <- insérer(obj, gauche(a), clé-fonc, <)
    renvoyer a
  sinon si <(clé-fonc(données(a)), clé-fonc(obj))
  alors
    droite(a) <- insérer(obj, droite(a), clé-fonc, <)
    renvoyer a
  sinon erreur("l'objet est déjà dans l'arbre")

L'opération d'insertion doit renvoyer le nouvel arbre, car on ne peut pas garantir la possibilité de modifier l'arbre passé en argument. C'est une conséquence directe de la représentation de l'arbre vide par NIL.

La version précédente suppose non seulement que les clés soient unique, mais aussi que pour remplacer un objet par un autre objet avec la même clé, il faut d'abord supprimer, puis insérer. On peut envisager la possibilité de remplacer automatiquement l'objet s'il en existe déjà un avec la même clé :

arbre
insérer(objet obj, arbre a, fonction clé-fonc, fonction <)
  si a = nil
  alors renvoyer créer-sommet(obj, nil, nil)
  sinon si <(clé-fonc(obj), clé-fonc(données(a)))
  alors 
    gauche(a) <- insérer(obj, gauche(a), clé-fonc, <)
    renvoyer a
  sinon si <(clé-fonc(données(a)), clé-fonc(obj))
  alors
    droite(a) <- insérer(obj, droite(a), clé-fonc, <)
    renvoyer a
  sinon 
    données(a) <- obj
    renvoyer a

La version précédente ne permet pas par contre de déterminer si un objet a été remplacé. Pour cela, on peut à nouveau envisager une deuxième valeur de retour :

arbre, booléen 
insérer(objet obj, arbre a, fonction clé-fonc, fonction <)
  si a = nil
  alors renvoyer créer-sommet(obj, nil, nil), faux
  sinon si <(clé-fonc(obj), clé-fonc(données(a)))
  alors 
    gauche(a), drapeau <- insérer(obj, gauche(a), clé-fonc, <)
    renvoyer a, drapeau
  sinon si <(clé-fonc(données(a)), clé-fonc(obj))
  alors
    droite(a), drapeau <- insérer(obj, droite(a), clé-fonc, <)
    renvoyer a, drapeau
  sinon 
    données(a) <- obj
    renvoyer a, vrai

On peut même laisser au client déterminer la méthode (erreur ou remplacer) avec un argument booléen de plus :

arbre, booléen 
insérer(objet obj, arbre a, fonction clé-fonc, fonction <, booléen erreur-si-existe)
  si a = nil
  alors renvoyer créer-sommet(obj, nil, nil), faux
  sinon si <(clé-fonc(obj), clé-fonc(données(a)))
  alors 
    gauche(a), drapeau <- insérer(obj, gauche(a), clé-fonc, <, erreur-si-existe)
    renvoyer a, drapeau
  sinon si <(clé-fonc(données(a)), clé-fonc(obj))
  alors
    droite(a), drapeau <- insérer(obj, droite(a), clé-fonc, <, erreur-si-existe)
    renvoyer a, drapeau
  sinon si erreur-si-existe
  alors
    erreur("l'objet est déjà dans l'arbre")
  sinon
    données(a) <- obj
    renvoyer a, vrai

Suppression d'un objet à partir d'une clé

Supprimer un objet à partir d'une clé dans un arbre de recherche est une opération assez complexe. Si l'objet est une feuille, cela ne pose pas de problème, mais si c'est un sommet intérieur, il faut réorganiser l'arbre de manière a préserver les propriétés de l'arbre binaire de recherche.

Nous allons commencer par deux autres algorithmes, plus simples, qui seront utilisés par l'algorithme de suppression, mais qui seront également utiles pour implémenter certains types abstraits, à savoir chercher et supprimer l'élément maximum, et chercher et supprimer l'élément minimum de l'arbre.

Ces deux opération doivent renvoyer l'objet, mais également le nouvel arbre après la suppression pour la raison évoquée ci-dessus, à savoir la représentation de l'arbre vide par NIL.

objet, arbre
chercher-et-supprimer-max(arbre a)
  assert(a != nil)
  si gauche(a) = nil & droite(a) = nil
  alors renvoyer donées(a), nil
  sinon si droite(a) = nil
  alors renvoyer données(a), gauche(a)
  sinon
    max, droite(a) <- chercher-et-supprimer-max(droite(a))
    renvoyer max, a
objet, arbre
chercher-et-supprimer-min(arbre a)
  assert(a != nil)
  si gauche(a) = nil & droite(a) = nil
  alors renvoyer donées(a), nil
  sinon si gauche(a) = nil
  alors renvoyer donées(a), droite(a)
  sinon
    min, gauche(a) <- chercher-et-supprimer-min(gauche(a))
    renvoyer min, a

Voici la première version de l'opération de suppression. Pour supprimer un objet dans un sommet dont le sous arbre gauche n'est pas vide, on remplace l'objet stocké dans le sommet par l'objet maximum de ce sous arbre gauche et on le supprime de celui-ci. Pour supprimer un objet dans un sommet dont le sous arbre droite n'est pas vide, on remplace l'objet stocké dans le sommet par l'objet minimum de ce sous arbre droite et on le supprime de celui-ci.

arbre
supprimer(objet clé, arbre a, fonction clé-fonc, fonction <)
  assert(a != nil)
  si <(clé, clé-fonc(donées(a)))
  alors 
    gauche(a) <- supprimer(clé, gauche(a), clé-fonc, <)
    renvoyer a
  sinon si <(clé-fonc(données(a)), clé)
  alors 
    droite(a) <- supprimer(clé, droite(a), clé-fonc, <)
    renvoyer a
  sinon si gauche(a) != nil
  alors
    max, gauche(a) <- chercher-et-supprimer-max(gauche(a))
    données(a) <- max
    renvoyer a
  sinon si droite(a) != nil
    min, droite(a) <- chercher-et-supprimer-min(droite(a))
    données(a) <- min
    renvoyer a
  sinon
    renvoyer nil

La version ci-dessus est inutilement coûteuse, car pour supprimer un sommet dont l'un des deux sous arbre est vide, il suffit de renvoyer l'autre sous arbre :

arbre
supprimer(objet clé, arbre a, fonction clé-fonc, fonction <)
  assert(a != nil)
  si <(clé, clé-fonc(donées(a)))
  alors 
    gauche(a) <- supprimer(clé, gauche(a), clé-fonc, <)
    renvoyer a
  sinon si <(clé-fonc(données(a)), clé)
  alors 
    droite(a) <- supprimer(clé, droite(a), clé-fonc, <)
    renvoyer a
  sinon si gauche(a) = nil
  alors renvoyer droite(a)
  sinon si droite(a) = nil
  alors renvoyer gauche(a)
  sinon
    max, gauche(a) <- chercher-et-supprimer-max(gauche(a))
    données(a) <- max
    renvoyer a

Comme pour l'insertion, on peut envisager des variations. Dans les versions précédentes, une exception est levée lorsque aucun objet dans l'arbre ne corresponde à la clé indiquée. On peut envisager de renvoyer un deuxième argument de type booléen indiquant si l'objet à été trouvé et supprimé ou si aucun objet avec la clé indiquée n'existe.