Réviser les arbres binaires en NSI en 2 semaines

Les arbres binaires sont une structure de données incontournable en NSI, que ce soit en Première ou en Terminale. Pas de panique : avec un peu d'organisation, tu peux les maîtriser en deux semaines. Cet article te propose un plan de révision pas à pas, avec des exemples concrets en Python et des astuces pour le bac.

Semaine 1 : les bases des arbres binaires

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure hiérarchique où chaque nœud a au plus deux enfants : un gauche et un droit. Le nœud tout en haut s'appelle la racine, et les nœuds sans enfants sont les feuilles. En Python, on peut le représenter avec une classe simple :

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche
        self.droit = droit

Par exemple, pour créer un arbre avec 1 comme racine, 2 à gauche et 3 à droite :

arbre = Noeud(1, Noeud(2), Noeud(3))

Les parcours : profondeur d'abord

Il existe trois parcours en profondeur : préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et postfixe (gauche, droite, racine). Voici comment les implémenter récursivement :

def prefixe(noeud):
    if noeud:
        print(noeud.valeur)
        prefixe(noeud.gauche)
        prefixe(noeud.droit)

def infixe(noeud):
    if noeud:
        infixe(noeud.gauche)
        print(noeud.valeur)
        infixe(noeud.droit)

def postfixe(noeud):
    if noeud:
        postfixe(noeud.gauche)
        postfixe(noeud.droit)
        print(noeud.valeur)

Exercices pratiques

Pour t'entraîner, construis un arbre de taille 5 et affiche ses valeurs avec les trois parcours. Vérifie que tu obtiens le bon ordre. Tu peux aussi utiliser les exercices en ligne pour t'auto-évaluer.

Semaine 2 : arbres binaires de recherche (ABR)

Propriété fondamentale

Un arbre binaire de recherche (ABR) est un arbre binaire où, pour chaque nœud, tous les éléments du sous-arbre gauche sont plus petits que le nœud, et tous ceux du sous-arbre droit sont plus grands. Cette propriété permet une recherche rapide.

Insertion dans un ABR

Voici une fonction d'insertion récursive en Python :

def inserer(racine, valeur):
    if racine is None:
        return Noeud(valeur)
    if valeur < racine.valeur:
        racine.gauche = inserer(racine.gauche, valeur)
    else:
        racine.droit = inserer(racine.droit, valeur)
    return racine

Teste-la en insérant les valeurs 5, 3, 7, 2, 4, 6, 8 dans un arbre vide. Le résultat doit être un ABR équilibré.

Recherche dans un ABR

def rechercher(racine, valeur):
    if racine is None or racine.valeur == valeur:
        return racine
    if valeur < racine.valeur:
        return rechercher(racine.gauche, valeur)
    else:
        return rechercher(racine.droit, valeur)

La complexité est en O(log n) en moyenne, mais peut dégénérer en O(n) si l'arbre est déséquilibré (par exemple si on insère des valeurs triées).

Cas d'usage concret

Les ABR sont utilisés dans les dictionnaires (comme les dict de Python, mais en interne ce sont des tables de hachage) ou les index de bases de données. En NSI, tu les retrouveras dans des problèmes de recherche et de tri.

Conseils pour le bac NSI

À l'épreuve, on te demandera souvent de manipuler des arbres : implémenter un parcours, insérer ou rechercher dans un ABR. Entraîne-toi à écrire du code à la main sur papier. Utilise les fiches de révision pour retenir les algorithmes clés. N'oublie pas de consulter le cours complet pour approfondir.

Pour une aide personnalisée, n'hésite pas à visiter AlloBac ou AlloLycée pour des ressources complémentaires.

Conclusion

En deux semaines, tu peux passer de débutant à à l'aise avec les arbres binaires. Le secret ? Pratiquer un peu chaque jour, et ne pas hésiter à revenir sur les bases. Tu vas y arriver !