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é.
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
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 :
récupérer la clé d'un objet à partir de l'objet même, et
déterminer si une clé est inférieure à une autre clé.
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é.
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 à
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)
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
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.