Qu'est-ce qu'un arbre binaire de recherche ?
En NSI, tu as déjà dû rencontrer les listes et les dictionnaires. L'arbre binaire de recherche (ABR) est une autre structure de données fondamentale, particulièrement efficace pour stocker et retrouver des informations. Imagine un arbre généalogique, mais où chaque "parent" (qu'on appelle un nœud) a au maximum deux "enfants" : un à gauche et un à droite. La magie de l'ABR réside dans une règle simple mais puissante qui organise ces nœuds.
La propriété fondamentale d'un ABR est la suivante : pour tout nœud, toutes les valeurs de son sous-arbre gauche sont strictement inférieures à sa propre valeur, et toutes les valeurs de son sous-arbre droit sont strictement supérieures. Cette organisation hiérarchique est ce qui rend les recherches si rapides !
Les propriétés fondamentales d'un ABR
Pour bien comprendre et manipuler un ABR, il faut maîtriser ses règles de construction. Voici les trois propriétés principales :
- Structure d'arbre binaire : Chaque nœud possède au plus deux enfants (le gauche et le droit).
- Ordre des valeurs : La valeur d'un nœud est toujours supérieure à toutes les valeurs de son sous-arbre gauche et inférieure à toutes les valeurs de son sous-arbre droit.
- Unicité (générale) : Dans la plupart des cas, on considère que toutes les valeurs stockées dans l'arbre sont uniques. Certaines implémentations gèrent les doublons, mais c'est plus rare.
Cette organisation permet de diviser l'espace de recherche par deux à chaque étape lorsque l'on parcourt l'arbre, un peu comme une recherche dichotomique mais dans une structure arborescente.
Implémenter un ABR en Python
Voyons maintenant comment donner vie à cette théorie en code. Nous allons créer une classe pour représenter un nœud, puis une classe pour gérer l'arbre entier.
La classe Noeud
Chaque nœud est un objet qui contient sa valeur et des références vers ses enfants.
class Noeud: def __init__(self, valeur): self.valeur = valeur self.gauche = None self.droit = None
La classe ArbreBinaireRecherche
Cette classe contient la racine de l'arbre et les méthodes pour le manipuler.
class ArbreBinaireRecherche: def __init__(self): self.racine = None def est_vide(self): return self.racine is None
Les opérations essentielles : recherche, insertion, parcours
Rechercher une valeur
Pour chercher une valeur, on compare avec la racine. Si elle est plus petite, on explore le sous-arbre gauche ; si elle est plus grande, le sous-arbre droit. On répète jusqu'à trouver la valeur ou atteindre une feuille (None).
def rechercher(self, valeur_cible): return self._rechercher_noeud(self.racine, valeur_cible) def _rechercher_noeud(self, noeud_courant, valeur_cible): if noeud_courant is None or noeud_courant.valeur == valeur_cible: return noeud_courant if valeur_cible < noeud_courant.valeur: return self._rechercher_noeud(noeud_courant.gauche, valeur_cible) else: return self._rechercher_noeud(noeud_courant.droit, valeur_cible)
Insérer une nouvelle valeur
L'insertion suit la même logique que la recherche pour trouver l'emplacement correct (une feuille vide) où ajouter le nouveau nœud, en respectant la propriété d'ordre.
Parcourir l'arbre
Il existe trois principaux ordres de parcours (récursifs) qui visitent tous les nœuds :
- Infixe (en ordre) : Gauche → Racine → Droit. Donne les valeurs triées par ordre croissant !
- Préfixe : Racine → Gauche → Droit. Utile pour copier l'arbre.
- Postfixe : Gauche → Droit → Racine. Utile pour supprimer l'arbre.
Complexité et importance en NSI
La performance d'un ABR dépend grandement de sa forme. Dans le meilleur cas (arbre équilibré), la hauteur est logarithmique par rapport au nombre de nœuds (n). Les opérations de recherche, insertion et suppression ont alors une complexité en O(log n), ce qui est excellent.
Cependant, dans le pire cas (si les valeurs sont insérées dans l'ordre croissant ou décroissant), l'arbre dégénère en une simple liste chaînée. Sa hauteur devient n, et les opérations tombent à O(n), comme une recherche séquentielle dans une liste.
C'est pour pallier ce problème que des variantes plus avancées comme les arbres AVL ou les arbres rouge-noir ont été inventées. Elles maintiennent l'arbre équilibré automatiquement après chaque insertion ou suppression. Les ABR sont une porte d'entrée indispensable vers ces structures plus complexes que tu pourras étudier en spécialité NSI ou dans le supérieur.
Maîtriser les ABR, c'est comprendre un pilier de l'algorithmique et des structures de données. Cela te sera utile non seulement pour le bac en NSI, mais aussi pour aborder sereinement des sujets comme les bases de données ou les algorithmes de tri et de recherche plus efficaces.
