NSI Terminale

Arbre Binaire de Recherche


Nous avons vu que la recherche dans un Arbre Binaire était plus efficace lorsqu'on sait où chercher.

Le coût est alors fonction de la hauteur h de 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.

Nous avons 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. Mais il ne s'agit pas vraiment d'une recherche d'une clé, juste de la localisation d'un noeud par rapport à un autre.

Nous allons voir aujourd'hui un Arbre conçu spécifiquement pour pouvoir savoir où chercher la clé qui nous intéresse.

Prérequis :

  • Données : Arbre et Arbre Binaire
  • Algos : Parcours d'Arbres
  • Algos : Algorithmes des Arbres Binaires

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 sont plus petites* que la clé de la racine de l'Arbre étudié
  2. Toutes les clés du sous-arbre de droite sont 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.

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.

Et maintenant une petite video :

01° Vérifier que toutes les clés à gauche du Noeud de clé 20 sont inférieures à 20 et que tous les Noeuds dont la clé est supérieure à 20 est dans le sous-arbre droite de l'arbre de racine 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 : le noeud-père du Noeud de clé 17 est directement le Noeud de clé 20.

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

L'algorithme proposé consiste à mémoriser la position en cours (dans arbre) et la position de l'étape précédente (dans arbre_parent).

Algorithme d'insertion d'un noeud dans un Arbre Binaire de Recherche NON VIDE

ENTREE 1 : l'ABR arbre (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 ici l'arbre sur place

inserer_noeud_dans_ABR(arbre:ABR, nd:Noeud) -> Vide

    étape 1 : on crée arbre_parent, variable qui va contenur 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 dans le pire des cas θ(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 permettant d'insérer un noeud (ou un autre algorithme mais réalisant la même chose) sans regarder vos notes.

Coût de l'insertion dans un Arbre Binaire de Recherche

Le coût est 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.

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é 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é. 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): 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é ou VIDE

recherche(arbre:ABR, cr:Cle) -> Noeud|Vide

A vous d'agir !

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

    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 que dans ce cas, le coût de l'insertion et de la recherche est θ(log2(n)).

Or, ce cas est assez rare cas il faut déjà au moins que le nombre de noeuds soit égal à une puissance de 2 moins 1 : 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. En 1962 que 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, pour tout nœud de l'arbre, la différence entre les hauteurs de ses deux fils ne peut excéder 1..

Cet Arbre n'est pas un Arbre Binaire équilibré (je considère une hauteur de 0 pour une racine seule)

ABR pas équilibré

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

ABR équilibré

Pour un Arbre Binaire équilibré, on considère que le coût d'une recherche ou d'une insertion est au pire 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 un code un peu plus "pur". Dans le cas présenté (plutôt simple et clair), on a une boucle non bornée qu'on coupe non pas à cause de sa condition propre mais à cause du retour qui provoque la sortie de l'algorithme.

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

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

Activité publiée le 26 02 2021
Dernière modification : 26 02 2021
Auteur : Andjekel
Sources : ows. h. et NSI4NOOBS