Exercice : Implémentation des ABR [Spécialité NSI - Année 2026

Implémentation des ABR

Ce TP a pour but de vous aider à implémenter les arbres binaires de recherche en Python.

Nous allons donc utiliser une classe ABR qui contient un attribut arbre faisant référence au noeud racine (classe Noeud) de l'arbre, ou à None si l'arbre est vide.

class Noeud:
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit = d
class ABR:
    def __init__(self):
        self.arbre = None

class Noeud:
    def __init__(self, g, v, d):
        self.gauche = g
        self.valeur = v
        self.droit = d

class ABR:
    def __init__(self):
        self.arbre = None

Question

Avant d'ajouter des valeurs dans notre ABR, nous allons apprendre à s'en servir pour chercher si un élément est présent dans un ABR ou non.

Rédiger une méthode rechercher() qui prend en paramètre une valeur et renvoie True si la valeur est présente, False sinon.

Testez votre code avec l'exemple dans l'indice.

Indice

arbre1 = ABR()
arbre1.arbre = Noeud(Noeud(Noeud(None, 1, None), 2, Noeud(None, 4, None)), 6, Noeud(Noeud(None, 7, None), 9, None))        

arbre1 = ABR()
arbre1.arbre = Noeud(Noeud(Noeud(None, 1, None), 2, Noeud(None, 4, None)), 6, Noeud(Noeud(None, 7, None), 9, None))

Question

Désormais, attaquons-nous à l'ajout d'éléments dans notre arbre binaire.

Rédiger une méthode ajouter() qui prend en paramètre une valeur et ajoute la valeur dans l'ABR si elle n'est pas déjà présente.

Question

Expliquer quelle est la complexité (le coût) de la recherche et de l'ajout d'une valeur dans un arbre binaire de recherche.

Dans le pire des cas, que vaut cette valeur ? À quel algorithme cela vous fait penser ?

Fin

Afin d'optimiser les abres binaires, on va s'assurer lors de leur construction de ne pas impacter la complexité de recherche d'une valeur.

Mais c'est hors-programme, alors si ça vous intéresse, consultez les arbres rouges-noirs ou AVL.

Question

Pour les plus rapides :

Écrire une méthode minimum() qui renvoie la valeur minimale présente dans un ABR. De même pour maximum().
Écrire une fonction trier() qui prend en parmètre une liste et trie cette liste en utilisant les arbres binaires de recherche. Quelle est son efficacité ?