18 - Arbre Binaire de Recherche
Nous avons vu que la recherche dans un Arbre Binaire était plus efficace lorsqu'on sait où chercher. Dans ce cas, le coût est linéaire par rapport à la hauteur h de l'Arbre Binaire : la complexité peut donc s'écrire 𝓞(h). Du coup,
- Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
- Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
- Si l'AB est quelconque, on est entre les deux.
Nous avons également vu qu'une implémentation des noeuds dans un tableau permet de trouver un noeud à coût constant pourvu qu'on connaisse parfaitement sa localisation. Il s'agit juste de la localisation d'un noeud par rapport à un autre, pas d'une recherche de clé.
Nous allons voir aujourd'hui un Arbre conçu spécifiquement pour pouvoir savoir où chercher facilement la clé qui nous intéresse.
Logiciel nécessaire pour l'activité : -
Prérequis :
- Données : Arbre et Arbre Binaire
- Algos : Parcours d'Arbres
- Algos : Algorithmes des Arbres Binaires
Evaluation ✎ :
Documents de cours : open document ou pdf
Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)
1 - Arbre Binaire de Recherche (ABR)
Définition d'un Arbre Binaire de Recherche
Un Arbre Binaire de Recherche est un Arbre Binaire qui respecte une organisation ordonnéee particulière.
Les clés des Noeuds doivent toutes pouvoir être comparées entre elles (c'est à dire disposer d'un opérateur < ou > ...).
La définition de l'Arbre Binaire de recherche impose que :
- toutes les clés du sous-arbre gauche soient plus petites* que la clé de la racine de l'Arbre étudié
- toutes les clés du sous-arbre de droite soient plus grandes* que la clé de la racine de l'Arbre étudié
La présence du * indique que l'égalité peut être traitée comme vous le voulez : à vous de choisir si vous voulez insérer un tel noeud à droite ou à gauche. Dans un premier temps, nous nous limiterons au cas des arbres pour lequel les clés sont toutes différentes.
On notera qu'on peut également faire l'inverse : mettre les plus grandes à gauche et les plus petites à droite.
Exemples
Un Arbre Binaire de Recherche Complet :
Les mêmes noeuds avec les mêmes clés dans une configuration moins optimale pour la recherche :
L'intérêt ?
Comme pour la liste-tableau trié qui permet une recherche dichotomique à coût logarithmique plutôt que linéaire, l'ABR permet une recherche à coût logarithmique (sur un Arbre proche d'un Arbre Complet) plutôt que linéaire.
En Anglais
En anglais, on dit Binary Search Tree ou BST.
01° Vérifier que
- toutes les clés à gauche du Noeud de clé 20 sont inférieures à 20 et
- toutes les clés à droite du Noeud de clé 20 sont supérieures à 20
02° Créer un nouvel Arbre Binaire de Recherche (ABR) un peu moins optimisé pour la recherche mais comportant les mêmes clés : la racine 20 mène ç gauche à 17 et à droite à 26.
Trouver deux versions du sous-arbre gauche possibles.
Pourquoi cet Arbre est-il moins optimisé pour la recherche ?
...CORRECTION...
Ou encore
Il est moins optimisé que l'Arbre Binaire Complet puisqu'il possède un étage en plus : la recherche du noeud de clé 9 sera plus longue d'une étape.
Création progressive d'un ABR
On commence par la racine puis on positionne progressivement les autres éléments, un à la fois.
Pour rajouter les noeuds (dont on connaît la clé) proposés, on suit ce principe :
- Partir de la racine
- Si la clé à placer est inférieure à celle du noeud actuel, on place la clé à gauche si le sous-arbre gauche est vide, sinon on répète l'opération en partant de la racine du sous-arbre gauche.
- Si la clé à placer est supérieure ou égale à celle du noeud actuel, on place la clé à droite si le sous-arbre droite est vide, sinon on répète l'opération en partant de la racine du sous-arbre droite.
Exemple
On part de 50 et on rajoute 30.
On rajoute ensuite 45.
Puis 65.
Puis éventuellement à nouveau 65.
On notera donc qu'il faut faire très attention au cas des ABR lorsque des noeuds peuvent porter la même clé. Il existe des algorithmes d'insertion plus performants qui permettent de limiter la hauteur des AB si on rajoute plusieurs fois des clés identiques. On ne s'en préoccupera pas cette année.
04° Créer un nouvel Arbre Binaire de Recherche (ABR) dont les clés suivantes sont insérées progressivement : 32-16-8-35-33.
...CORRECTION...
05° Même question en modifiant la place du 35 : 35-32-16-8-33.
L'ordre d'apparition des clés est-elle importante avec ce principe d'insertion ?
...CORRECTION...
L'ordre des clés est effectivement à surveiller : on n'obtiendra pas le même arbre avec une séquence différente.
06° Utiliser le site proposé pour visualiser l'insertion de 33-35-16-8-32.
https://www.cs.usfca.edu/~galles/visualization/BST.html
2 - Algorithme d'insertion
Nous allons maintenant voir comment réaliser avec un algorithme ce que vous avez fait juste au dessus. La différence fondamentale avec les petits exercices ci-dessus est qu'on va chercher à insérer un Noeud qui possède une Clé ainsi que d'autres données éventuelles, et pas à insérer un Noeud créé pour l'occasion et ne contenant que la Clé.
Pour cela, nous allons avoir besoin des fonctions d'interface (ou primitives) vues précédemment mais également de deux nouvelles fonctions permettant d'insérer un nouvel Arbre Binaire de Recherche à gauche ou à droite :
Les fonctions liées aux Noeuds :
- nvND(cle:Cle, data:Data) -> Noeud : renvoie la référence d'un nouveau noeud.
- cle(noeud:Noeud) -> Cle : renvoie la clé du noeud.
- data(noeud:Noeud) -> Data : renvoie les données associées au noeud.
Les fonctions liées à l'Arbre Binaire de Recherche lui-même :
- nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
- nvABR(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE de RECHERCHE dont la racine est r et dont les sous-arbres sont g et d fournis.
- estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
- racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
- gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
- droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.
- inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
- inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.
Les deux nouvelles fonctions liées à l'insertion :
Regardons maintenant comment traduire l'insertion sous forme d'un algorithme.
Algorithme d'insertion d'un noeud dans un Arbre Binaire de Recherche NON VIDE
L'algorithme proposé consiste à
- se déplacer récursivement dans l'arbre jusqu'à ce que l'arbre soit un emplacement vide, un arbre vide
- mémoriser dans arbre_parentl'arbre qui mène à cet emplacement vide
ENTREE 1 : l'ABR arbre (précondition : non vide) avec lequel on veut travailler
ENTREE 2 : le noeud nd (possèdant une clé c et des données annexes éventuelles) qu'on veut rajouter à notre arbre.
SORTIE : Vide, on modifie juste l'arbre sur place
inserer_noeud_dans_ABR(arbre:ABR, nd:Noeud) -> Vide
étape 1 : on crée arbre_parent, variable qui va contenir la référence de l'arbre où insérer le Noeud nd
arbre_parent ← Vide
étape 2 : on explore l'arbre jusqu'à trouver la bonne position
TANT QUE NON estArbreVide(arbre)
arbre_parent ← arbre
SI cle(nd) < cle(racine(arbre))
arbre ← gauche(arbre)
SINON
arbre ← droite(arbre)
Fin SI
Fin Tant Que
étape 3 : on insère l'arbre dont nd est la racine au bon endroit
SI cle(nd) < cle(racine(arbre_parent))
inserer_gauche(arbre_parent, nvABR(nd, nvAV(), nvAV()) )
SINON
inserer_droite(arbre_parent, nvABR(nd, nvAV(), nvAV()) )
Fin SI
Renvoyer VIDE
07° Quels sont les coûts des étapes 1, 2 et 3 ? Quel est le coût de l'insertion d'un nouveau noeud dans un ABR (par rapport à la hauteur de l'ABR) ?
...CORRECTION...
Etape 1 : Coût constant 𝓞(1).
Etape 2 : Coût linéaire en fonction de la hauteur h de l'arbre 𝓞(h).
Etape 3 : Coût constant 𝓞(1).
Au total, l'insertion est donc LINEAIRE par rapport à la hauteur h de l'ABR.
08° Exécuter l'algorithme pour insérer 31 dans cet Arbre :
Que contiennent les clés des racines de arbre_parent et arbre à chaque tour dans la boucle TANT QUE puis à la fin de l'algorithme ?
...CORRECTION...
On commence par une racine vide pour arbre_parent et une clé 33 pour arbre.
Ensuite, on rentre dans la boucle TANT QUE.
1er tour de boucle :
- arbre_parent possède la clé 33
- arbre possède la clé 16
1er tour de boucle :
- arbre_parent possède la clé 16
- arbre possède la clé 32
3e tour de boucle :
- arbre_parent possède la clé 32
- arbre ne possède pas de clé car il fait référence à un arbre vide
On sort donc de la boucle.
A la fin des boucles, on voit donc qu'on va insérer le nouveau noeud sur le noeud-parent 32 puisque arbre_parent possède la clé 32.
09° Retrouver l'algorithme inserer_noeud_dans_ABR() permettant d'insérer un noeud sans regarder vos notes.
Coût de l'insertion dans un Arbre Binaire de Recherche
C'est comme pour la recherche.
Le coût est fonction de la hauteur h l'Arbre Binaire : inserer_noeud_dans_ABR(h). Du coup,
- Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
- Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
- Si l'AB est quelconque, on est entre les deux.
9B° Trouver un algorithme inserer_noeud_dans_ABR() avec TANT QUE où on a pas besoin de mémoriser le parent : on teste directement dans le TANT QUE que l'emplacement voulu est bien vide, ou pas.
9C° Trouver l'algorithme récursif inserer_noeud_dans_ABR(). Indice : le cas de base consiste à constater que l'emplacement gauche est vide si la clé est plus petite que la clé de la racine actuelle, et même chose avec supérieure sur l'arbre droite.
3 - Algorithme de recherche
Comme nous l'avons vu, il est facile de trouver la prochaine étape lorsqu'on cherche une clé dans un ABR : on compare la clé cherchée avec la clé du noeud actuel, et on sait si on doit aller à droite ou à gauche. L'Arbre Binaire de Recherche permet donc de faire des ... recherches ciblées. C'est le but. Nous allons donc retrouver le fait que :
Coût de la recherche dans un Arbre Binaire de Recherche
Le coût est alors fonction de la hauteur h l'Arbre Binaire : 𝓞(h). Du coup,
- Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
- Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
- Si l'AB est quelconque, on est entre les deux.
10° Proposer un algorithme permettant de rechercher un noeud dans un ABR.
On travaillera à partir des indications ci-dessous :
Dans un Arbre Binaire de Recherche, la recherche d'une Clé recherchée cr est ciblée : il suffit de comparer la valeur de la clé cr cherchée et la valeur de la clé c du noeud actuel pour savoir où aller ensuite.
Inutile donc de faire une recherche linéaire en profondeur ou en largeur : on utilise ces méthodes d'exploration lorsqu'on ne sait pas où chercher justement.
- Si l'arbre actuel est un arbre vide, on renvoie une réponse VIDE.
- Si c'est la bonne clé (cr == c), on a trouvé. On renvoie alors le Noeud de la racine de l'arbre actuel.
- Si la clé cherchée est plus petite que la clé du noeud (cr < c): arbre devient le sous-arbre de gauche.
- Si la clé cherchée est plus grande que la clé du noeud (cr > c): arbre devient le sous-arbre de droite.
Algorithme de recherche
ENTREE 1 : un Arbre Binaire de Recherche arbre
ENTREE 2 : une Clé cr
SORTIE : la référence d'un Noeud portant cette clé ou VIDE
recherche(arbre:ABR, cr:Cle) -> Noeud|Vide
A vous d'agir !
Voici la correction :
Algorithme de recherche dans un ABR : version itérative
Dans un Arbre Binaire de Recherche, la recherche d'une Clé cr est ciblée : inutile de faire une recherche linéaire en profondeur ou en largeur. Il suffit de comparer la valeur de la clé cr cherchée et la valeur de la clé c du noeud actuel pour savoir où aller ensuite.
- Si l'arbre actuel est un arbre vide, on renvoie une réponse VIDE.
- Si c'est la bonne clé (cr == c), on a trouvé.
- Si la clé cherchée est plus petite que la clé du noeud (cr < c): on va à gauche.
- Si la clé cherchée est plus grande que la clé du noeud (cr > c): on va à droite.
Algorithme de recherche
ENTREE 1 : un Arbre Binaire de Recherche arbre
ENTREE 2 : une Clé cr
SORTIE : la référence d'un Noeud portant cette clé
recherche(arbre:ABR, cr:Cle) -> Noeud|Vide
TANT QUE NON estArbreVide(arbre)
SI cr == cle(racine(arbre))
Renvoyer racine(arbre)
SINON SI cr < cle(racine(arbre))
arbre ← gauche(arbre)
SINON SI cr > cle(racine(arbre))
arbre ← droite(arbre)
Fin SI
Fin Tant Que
Renvoyer VIDE
11° Appliquer cet algorithme sur cet arbre en cherchant 22.
12° Dans le pire des cas, quel est le coût de cet algortihme en fonction de la hauteur de l'arbre ? En fonction de la taille pour un arbre complet ?
...CORRECTION...
On retrouve un coût linéaire par rapport à la hauteur.
Pour un arbre complet, le coût est donc logarithmique base 2 par rapport à la taille puisqu'à chaque étape, on réduit approximativement par deux le nombre de noeuds à supprimer de la recherche.
ABR complet et ABR équilibré
Vous savez maintenant qu'un ABR est complet si le dernier étage est composé uniquement des feuilles de l'arbre.
Nous venons de voir plusieurs fois que dans le cas d'un arbre complet, le coût de l'insertion et de la recherche est 𝓞(log2(n)).
Or, ce cas est assez rare : il faut déjà que le nombre de noeuds soit exactement n = 2x - 1.
La notion d'arbre équilibré possède plusieurs variantes. L'important est de comprendre qu'il s'agit d'un arbre pour lequel les recherches peuvent toutes se ramener à peu près au cas de l'arbre complet. C'est le "à peu près" qui fera la différence entre les définitions qu'on peut trouver.
Nous allons en voir un qui date de 1962. Deux Russes, Adel'son-Vel'skii et Landis, introduisent des critères définissant un équilibre. Les arbres vérifiant ces critères sont connus sous le nom d'arbres AVL. Avec ce critère AVL, un arbre équilibré est un arbre pour lequel, pour tout nœud de l'arbre, la différence entre les hauteurs de ses deux sous-arbres ne peut excéder 1..
Exemple 1 : Cet Arbre n'est pas un Arbre Binaire équilibré : le noeud 17 possède à gauche un sous-arbre de hauteur 1 et à droite un sous-arbre de hauteur -1 (un arbre vide)
Exemple 2 : Par contre, cet Arbre est un Arbre Binaire équilibré :
Intérêt de la notion d'arbre équilibré ?
On considérera qu'un arbre binaire équilibré se comporte comme un arbre binaire complet lors des recherches et des insertions : le coût d'une recherche ou d'une insertion est logarithmique par rapport à la taille de l'arbre (𝓞(log2(n))).
Il existe bien d'autres façon de gérer un algorithme de recherche dans un ABR.
13° Proposer une version ne possédant qu'un seul retour. Cela permet d'obtenir des instructions sur lequelles on peut plus facilement réaliser la preuve de correction. Dans le cas présenté, on a une boucle non bornée TANT QUE qui va s'arrêter non pas à cause de sa condition d'arrêt propre mais à cause du retour qui provoque la sortie de l'algorithme ! Pas très propre...
recherche(arbre:ABR, cr:Cle) -> Noeud
TANT QUE NON estArbreVide(arbre)
SI cr == cle(racine(arbre))
Renvoyer racine(arbre)
SINON SI cr < cle(racine(arbre))
arbre ← gauche(arbre)
SINON SI cr > cle(racine(arbre))
arbre ← droite(arbre)
Fin SI
Fin Tant Que
Renvoyer VIDE
...CORRECTION...
reponse ← VIDE
TANT QUE NON estArbreVide(arbre)
SI cr == cle(racine(arbre))
reponse ← racine(arbre)
arbre ← VIDE
SINON SI cr < cle(racine(arbre))
arbre ← gauche(arbre)
SINON SI cr > cle(racine(arbre))
arbre ← droite(arbre)
Fin SI
Fin Tant Que
Renvoyer reponse
14° Proposer une version utilisant la récursivité. Pour cela, demandez-vous quels sont les cas de base (les cas où on peut répondre définitivement) et ce qu'il faut faire sur les cas récursifs.
Dans cette version, arbre pourra être un arbre vide.
recherche(arbre:ABR, cr:Cle) -> Noeud|Vide
TANT QUE NON estArbreVide(arbre)
SI cr == cle(racine(arbre))
Renvoyer racine(arbre)
SINON SI cr < cle(racine(arbre))
arbre ← gauche(arbre)
SINON SI cr > cle(racine(arbre))
arbre ← droite(arbre)
Fin SI
Fin Tant Que
Renvoyer VIDE
...CORRECTION...
recherche(arbre:ABR, cr:Cle) -> Noeud
SI estArbreVide(arbre)
Renvoyer VIDE
SINON SI cr == cle(racine(arbre))
Renvoyer racine(arbre)
SINON SI cr < cle(racine(arbre))
Renvoyer recherche(gauche(arbre), cr)
SINON SI cr > cle(racine(arbre))
Renvoyer recherche(droite(arbre), cr)
Fin SI
4 - FAQ
Les fonctions d'interface courantes d'un ABR (primitives)
Les fonctions liées aux Noeuds :
- nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
- cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
- data(noeud:Noeud) -> Data : renvoie les données associées au noeud.
Les fonctions liées à l'ABR lui-même :
- nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
- nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.
- estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
- racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre NON VIDE.
- gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre NON VIDE. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
- droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre NON VIDE.
- inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
- inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.
- recherche(arbre:ABR, cr:Cle) -> Noeud
- parent(arbre:Arbre) -> Arbre : renvoie le parent de arbre si il existe.
Activité publiée le 02 01 2021
Dernière modification : 30 01 2021
Auteur : ows. h.