Arbres binaires de recherche

Cours

Les arbres binaires de recherche (ABR) permettent de trouver très rapidement un élément dans un ensemble de valeurs.

Définition

Un arbre binaire de recherche est un arbre binaire où, pour chaque nœud de l'arbre :

• tous les nœuds qui composent le sous-arbre gauche ont une valeur strictement inférieure à la racine de l'arbre ;
• tous les nœuds qui composent le sous-arbre droit ont une valeur strictement supérieure à la racine de l'arbre.

Exercice

Cet exercice 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 nœud 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

Question n°1

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 ci-dessous :

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

Question n°2

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 n°3

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 - Hors programme

Afin d'optimiser les arbres 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 n°4

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 paramètre une liste et trie cette liste en utilisant les arbres binaires de recherche. Quelle est son efficacité ?