⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 3

Arbres et arbres binaires de recherche

Vocabulaire des arbres (racine, nœud, feuille, hauteur, taille), arbres binaires, implémentation, parcours en profondeur (préfixe, infixe, suffixe) et en largeur, arbres binaires de recherche : recherche, insertion et coût.

1. Vocabulaire

Définition

Un arbre est une structure hiérarchique formée de nœuds ; le nœud de départ est la racine, les nœuds sans enfant sont les feuilles. La taille est le nombre de nœuds ; la hauteur est le nombre de nœuds sur la plus longue branche (convention : hauteur $1$ pour une racine seule). Dans un arbre binaire, chaque nœud a au plus deux enfants : un sous-arbre gauche et un sous-arbre droit.

Arbre binaire de recherche : à gauche les clés plus petites, à droite les plus grandes.

2. Implémentation et parcours

Exemple · Classe Noeud

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

def taille(a):
    if a is None:
        return 0
    return 1 + taille(a.gauche) + taille(a.droit)

Propriété · Parcours en profondeur

Préfixe : nœud, puis gauche, puis droit. Infixe : gauche, nœud, droit. Suffixe : gauche, droit, nœud. Le parcours en largeur visite les nœuds niveau par niveau, à l'aide d'une file. Sur l'arbre du cours : infixe $1, 3, 4, 6, 7, 8, 10, 14$ ; largeur $8, 3, 10, 1, 6, 14, 4, 7$.

3. Arbres binaires de recherche (ABR)

Définition

Un ABR est un arbre binaire où, pour chaque nœud, les clés du sous-arbre gauche sont inférieures à sa clé et celles du sous-arbre droit supérieures. Son parcours infixe donne les clés triées.

Méthode · Recherche dans un ABR

def recherche(a, x):
    while a is not None:
        if x == a.cle:
            return True
        a = a.gauche if x < a.cle else a.droit
    return False

Propriété · Coût

La recherche et l'insertion suivent une seule branche : coût proportionnel à la hauteur $h$. Pour un arbre équilibré de $n$ nœuds, $h \approx \log_2 n$ ; pour un arbre « peigne » (clés insérées dans l'ordre), $h = n$.

Activité · Insérer dans un ABR

MatérielPython.

ConsigneÉcrire une fonction récursive inserer(a, x) qui renvoie l'arbre après insertion de x.

Résultat

def inserer(a, x):
    if a is None:
        return Noeud(x)
    if x < a.cle:
        a.gauche = inserer(a.gauche, x)
    else:
        a.droit = inserer(a.droit, x)
    return a

BilanL'ordre d'insertion détermine la forme de l'arbre, donc son efficacité.

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

Créer un compte gratuit Se connecter