Algo ABR

Identification

Infoforall

18 - Arbre Binaire de Recherche


ACTIVITE EN COURS DE TRANSFORMATION. Le but est d'utiliser l'implémentation qui est tombé plusieurs fois dans les sujets de BAC.

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,

  1. Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
  2. Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
  3. 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 :

  1. toutes les clés du sous-arbre gauche soient plus petites* que la clé de la racine de l'Arbre étudié
  2. 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 :

ABR complet

Les mêmes noeuds avec les mêmes clés dans une configuration moins optimale pour la recherche :

ABR quelconque

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
ABR complet

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...

ABR question 2

Ou encore

ABR question 2 version 2

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 :

  1. Partir de la racine
  2. 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.
  3. 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.

ABR 50-30

On rajoute ensuite 45.

ABR 50-30-45

Puis 65.

ABR 50-30

Puis éventuellement à nouveau 65.

ABR 50-30

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...

ABR question 4

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...

ABR question 5

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

Visualisation du site usfca.edu

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 :

  1. nvND(cle:Cle, data:Data) -> Noeud : renvoie la référence d'un nouveau noeud.
  2. cle(noeud:Noeud) -> Cle : renvoie la clé du noeud.
  3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'Arbre Binaire de Recherche lui-même :

  1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
  2. 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.
  3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
  4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
  5. 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.
  6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.
  7. Les deux nouvelles fonctions liées à l'insertion :

  8. inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
  9. inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.

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_parentVide


    étape 2 : on explore l'arbre jusqu'à trouver la bonne position

    TANT QUE NON estArbreVide(arbre)

      arbre_parentarbre

      SI cle(nd) < cle(racine(arbre))

        arbregauche(arbre)

      SINON

        arbredroite(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 ?

Visualisation du site usfca.edu

...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,

  1. Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
  2. Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
  3. 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,

  1. Si l'AB est complet, on obtient alors un coût logarithmique sur la taille de l'Arbre : 𝓞(log2(n))
  2. Si l'AB est filiforme, on retrouve juste un coût linéaire par rapport à la taille : 𝓞(n)
  3. 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.

  1. Si l'arbre actuel est un arbre vide, on renvoie une réponse VIDE.
  2. Si c'est la bonne clé (cr == c), on a trouvé. On renvoie alors le Noeud de la racine de l'arbre actuel.
  3. Si la clé cherchée est plus petite que la clé du noeud (cr < c): arbre devient le sous-arbre de gauche.
  4. 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.

  1. Si l'arbre actuel est un arbre vide, on renvoie une réponse VIDE.
  2. Si c'est la bonne clé (cr == c), on a trouvé.
  3. Si la clé cherchée est plus petite que la clé du noeud (cr < c): on va à gauche.
  4. 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))

        arbregauche(arbre)

      SINON SI cr > cle(racine(arbre))

        arbredroite(arbre)

      Fin SI

    Fin Tant Que

    Renvoyer VIDE

11° Appliquer cet algorithme sur cet arbre en cherchant 22.

ABR complet

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 ?

ABR 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.

ABR complet

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)

ABR pas équilibré

Exemple 2 : Par contre, cet Arbre est un Arbre Binaire équilibré :

ABR é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))

        arbregauche(arbre)

      SINON SI cr > cle(racine(arbre))

        arbredroite(arbre)

      Fin SI

    Fin Tant Que

    Renvoyer VIDE

...CORRECTION...

    reponse ← VIDE

    TANT QUE NON estArbreVide(arbre)

      SI cr == cle(racine(arbre))

        reponseracine(arbre)

        arbre ← VIDE

      SINON SI cr < cle(racine(arbre))

        arbregauche(arbre)

      SINON SI cr > cle(racine(arbre))

        arbredroite(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))

        arbregauche(arbre)

      SINON SI cr > cle(racine(arbre))

        arbredroite(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 :

  1. 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.
  2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
  3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'ABR lui-même :

  1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
  2. 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.
  3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
  4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre NON VIDE.
  5. 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.
  6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre NON VIDE.
  7. inserer_gauche(arbre:Arbre, g:Arbre) -> None : on remplace le sous-arbre gauche de arbre par l'arbre g.
  8. inserer_droite(arbre:Arbre, d:Arbre) -> None : on remplace le sous-arbre droite de arbre par l'arbre d.
  9. recherche(arbre:ABR, cr:Cle) -> Noeud
  10. parent(arbre:Arbre) -> Arbre : renvoie le parent de arbre si il existe.

La dernière activité traite de l'implémentation Python des algorithmes sur l'Arbre Binaire de Recherche.

Activité publiée le 02 01 2021
Dernière modification : 30 01 2021
Auteur : ows. h.