Aller au contenu principal

TP2 - Arbres binaires de recherche

Objectifs
  • Comprendre la structure d’un arbre binaire de recherche
  • Implémenter l’insertion et la recherche dans un ABR
  • Exploiter la propriété d’ordre d’un ABR
Pré-requis
  • Arbres binaires
  • Programmation orientée objet
  • Récursivité
Documentation

Pour chaque fonction créée, ne pas oublier de la documenter.

Le but de cette seconde partie est de modéliser un arbre binaire de recherche en Python à l’aide de la programmation orientée objet.

Nous allons construire une classe représentant un nœud binaire de recherche, héritant des propriétés d’un nœud binaire, puis implémenter différentes méthodes permettant d’obtenir des informations sur l’arbre.

Création de la classe NBR​

On souhaite définir une classe NBR (Nœud Binaire de Recherche) héritant de NoeudBinaire.
Ici, le constructeur ne prend qu’un seul paramètre : la valeur, et les fils gauche et droit seront initialisés à None.

  1. Créer la classe NBR héritant de NoeudBinaire puis implémenter son constructeur __init__ prenant en paramètre valeur, et initialisant les fils gauche et droit à None.
  2. Créer l'arbre suivant : et stocker la racine dans la variable arbre_binaire_recherche.
  3. Tester les méthodes taille et hauteur sur cet arbre.
  4. Afficher l'arbre en utilisant la fonction afficher_arbre.

Méthodes de classe​

Méthodes récursives

Toutes les méthodes à écrire doivent être récursives.

Insertion d’une valeur​

On souhaite insérer une valeur dans l’arbre tout en respectant les règles de l’ABR.

  1. Si on veut insérer les valeurs 2, 13, 9 et 20 dans arbre_binaire_recherche, où faudrait-il placer ces nouveaux noeuds ?
  2. En utilisant l'algorithme présenté dans le cours, écrire la méthode inserer_valeur(self, x) dans la classe NBR qui ajoute un noeud contenant la valeur x dans l’arbre binaire de recherche.
  3. Insérer successivement les valeurs 2, 13, 9 et 20 dans arbre_binaire_recherche, puis vérifier si l'arbre obtenu correspond bien au résultat de la question 5.

Recherche d’une valeur​

On souhaite maintenant écrire une méthode permettant de vérifier si un arbre contient bien une valeur x, sans parcourir tous les nœuds.

  1. En utilisant l'algorithme présenté dans le cours, écrire la méthode contient_valeur(self, x) dans la classe NBR qui retourne True si un noeud contenant la valeur x est présent dans l’arbre binaire de recherche, False sinon.
  2. Tester la méthode sur l'arbre arbre_binaire_recherche en vérifiant la présence des noeuds 4, 5 et 6.

Trace de recherche​

Dans cet exercice, on s'intéresse à l'affichage d'une trace de la recherche effectuée, en indiquant par quel noeud on passe, et si on se dirige à gauche ou à droite, à l'aide de print.

Exemple
>>> arbre_binaire_recherche.trace_recherche(7)
15
Gauche
6
Droite
7
>>> arbre_binaire_recherche.trace_recherche(16)
15
Droite
18
Gauche
17
Gauche
Introuvable
  1. Écrire la fonction trace_recherche(self,x) affichant les informations de recherche de la valeur x.
  2. Tester la méthode sur l'arbre arbre_binaire_recherche en vérifiant la présence des noeuds 4, 5 et 6.

Valeurs extrêmes​

On souhaite ici trouver la valeur minimale et maximale de l'ABR.

  1. Déterminer la valeur minimale et maximale de l'arbre arbre_binaire_recherche.
  2. Proposer un algorithme permettant de trouver les valeurs des extremums.
  3. Implémenter les méthodes valeur_minimale(self) et valeur_maximale(self) retournant respectivement la plus petite et la plus grande des valeurs d'un ABR, à l'aide de l'algorithme trouvé à la question précédente.
  4. Tester la méthode sur l'arbre arbre_binaire_recherche.

Structure triée​

Par définition, un ABR est une structure qui se veut triée.

  1. Identifier le parcours permettant d’obtenir les valeurs dans l’ordre croissant.
  2. Implémenter une méthode tri_par_arbre(self) retournant une liste triée depuis un ABR.
  3. Implémenter une méthode en dehors de la classe liste_vers_arbre(liste) prenant en paramètre une liste triée, et retournant un ABR contenant les valeurs de la liste.

    Aide : la racine de l'arbre doit être la valeur du milieu de la liste. La moitié gauche fera partie du sous-arbre gauche, la moitié droite fera partie du sous-arbre droit.

Différentes constructions d’ABR et impact sur la complexité​

La façon dont un arbre binaire de recherche est construit influence fortement l’efficacité des opérations de recherche et d’insertion.

Nous allons comparer deux cas extrêmes :

  • un ABR dégénéré
  • un ABR bien équilibré (complet)

ABR dégénéré​

Un ABR est dit dégénéré lorsqu’il ressemble à une liste chaînée : chaque nœud n’a qu’un seul fils.

  1. Construire un ABR en insérant successivement les valeurs de la liste 
    [1, 2, 3, 4, 5, 6, 7]
    dans un arbre initialement vide.
  2. Afficher l'arbre avec la fonction afficher_arbre. Quelle est sa hauteur ?
  3. En utilisant la méthode trace_recherche, compter le nombre de comparaisons effectuées pour rechercher la valeur 7 dans l'arbre.
  4. Dans le pire des cas, si on dispose de n noeuds, quelle serait la complexité de la recherche ?

ABR équilibré (ou presque complet)​

On souhaite maintenant construire un ABR dont la hauteur est minimale.

  1. À partir de la liste triée : 
    [1, 2, 3, 4, 5, 6, 7]
    utiliser la fonction liste_vers_arbre pour construire un ABR équilibré.
  2. Afficher l'arbre avec la fonction afficher_arbre. Quelle est sa hauteur ?
  3. À l’aide de la méthode trace_recherche, observer le nombre de comparaisons nécessaires pour rechercher la valeur 7.
  4. Quelle est la complexité de la recherche dans cet arbre en fonction du nombre de nœuds n ?

Comparaisons​

  1. Expliquer pourquoi la façon d’insérer les valeurs dans un ABR est déterminante pour ses performances.
  2. Faire des recherches sur 2 structures basées sur les ABR :
    • Les AVL ;
    • Les Red-Black Trees et expliquer en quelques phrases leur fonctionnement, et comment ces structures sont utilisées.
  3. Pourquoi, dans les bibliothèques et logiciels réels, utilise-t-on souvent des ABR auto-équilibrés (AVL, Red-Black trees) plutôt que des ABR simples ?