Arbres & ABR

Définitions illustrées

Voici les définitions illustrées sur l'arbre suivant :

          A          ← racine (profondeur 0)
         / \
        B   C        ← profondeur 1
       / \   \
      D   E   F    ← profondeur 2
         /
        G           ← feuille (profondeur 3)

Propriétés importantes

• Un arbre binaire de hauteur h contient au maximum 2^h+1 − 1 nœuds
• Un arbre binaire de hauteur h contient au minimum h + 1 nœuds (chemin dégénéré)
• La hauteur minimale d'un arbre de n nœuds est ⌊log₂(n)⌋
• Un arbre parfait (complet + tous les nœuds internes ont 2 fils) de hauteur h a exactement 2^h+1 − 1 nœuds et 2^h feuilles

La classe Noeud

En NSI, on représente un arbre binaire avec une classe Noeud :

class Noeud:
    """Représente un nœud d'un arbre binaire."""
    def __init__(self, valeur, gauche=None, droite=None):
        self.valeur = valeur    # donnée stockée dans le nœud
        self.gauche = gauche    # sous-arbre gauche (Noeud ou None)
        self.droite = droite    # sous-arbre droit  (Noeud ou None)

    def est_feuille(self):
        """Retourne True si le nœud est une feuille."""
        return self.gauche is None and self.droite is None

Construction d'un arbre (des feuilles vers la racine)

# On construit toujours de bas en haut (des feuilles vers la racine)
#        8           ← ABR : gauche < racine < droite
#       / \
#      3   10
#     / \    \
#    1   6   14

n1  = Noeud(1)
n6  = Noeud(6)
n14 = Noeud(14)
n3  = Noeud(3, gauche=n1, droite=n6)
n10 = Noeud(10, droite=n14)
racine = Noeud(8, gauche=n3, droite=n10)

# Accès aux valeurs
print(racine.valeur)          # 8
print(racine.gauche.valeur)   # 3
print(n6.est_feuille())       # True
print(n3.est_feuille())       # False

Représentation alternative : tuples imbriqués

Certains sujets de bac utilisent des tuples (valeur, gauche, droite) ou None pour l'arbre vide :

# Même arbre sous forme de tuples (valeur, fils_gauche, fils_droit)
arbre = (8,
          (3, (1, None, None), (6, None, None)),
          (10, None, (14, None, None)))

# Accès : arbre[0]=racine, arbre[1]=gauche, arbre[2]=droite
print(arbre[0])       # 8 (racine)
print(arbre[1][0])   # 3 (fils gauche de la racine)

Parcours en profondeur (DFS) — 3 variantes

Les parcours DFS explorent un sous-arbre entièrement avant de passer au suivant. L'ordre dépend de la position du Nœud (N) par rapport au sous-arbre Gauche (G) et au sous-arbre Droit (D).

1. Parcours préfixe (N → G → D)

Nœud d'abord, puis gauche, puis droite. Résultat : A B D E C F G

def prefixe(noeud):
    if noeud is None: return       # cas de base : arbre vide
    print(noeud.valeur)              # 1. Visiter le nœud
    prefixe(noeud.gauche)            # 2. Sous-arbre gauche
    prefixe(noeud.droite)            # 3. Sous-arbre droit

2. Parcours infixe (G → N → D)

Gauche, puis nœud, puis droite. Résultat : D B E A F C G

Propriété clé : sur un ABR, l'infixe donne les valeurs dans l'ordre croissant !

def infixe(noeud):
    if noeud is None: return
    infixe(noeud.gauche)             # 1. Sous-arbre gauche
    print(noeud.valeur)              # 2. Visiter le nœud
    infixe(noeud.droite)             # 3. Sous-arbre droit

3. Parcours postfixe (G → D → N)

Gauche, droite, puis nœud en dernier. Résultat : D E B F G C A

Application : évaluation d'arbres d'expression arithmétique (NPI), suppression de nœuds.

def postfixe(noeud):
    if noeud is None: return
    postfixe(noeud.gauche)           # 1. Sous-arbre gauche
    postfixe(noeud.droite)           # 2. Sous-arbre droit
    print(noeud.valeur)              # 3. Visiter le nœud

Parcours en largeur — BFS (Breadth-First Search)

Visite les nœuds niveau par niveau. Ce parcours n'est pas récursif — il utilise une file (deque).

Résultat : A B C D E F G

from collections import deque

def largeur(racine):
    if racine is None: return
    file = deque([racine])           # on enfile la racine
    while file:
        noeud = file.popleft()       # on défile
        print(noeud.valeur)           # on visite
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droite is not None:
            file.append(noeud.droite)

Tableau récapitulatif

Taille et hauteur

# ── TAILLE : nombre total de nœuds ──────────────────────────────
def taille(noeud):
    if noeud is None: return 0          # arbre vide → taille 0
    return 1 + taille(noeud.gauche) + taille(noeud.droite)
    # le 1 compte le nœud courant

# ── HAUTEUR : longueur du plus long chemin ──────────────────────
def hauteur(noeud):
    if noeud is None: return -1        # convention : arbre vide → -1
    return 1 + max(hauteur(noeud.gauche), hauteur(noeud.droite))
    # +1 pour l'arête vers ce nœud, max pour le chemin le plus long

Compter les feuilles

def nb_feuilles(noeud):
    if noeud is None: return 0
    if noeud.gauche is None and noeud.droite is None:
        return 1                         # c'est une feuille
    return nb_feuilles(noeud.gauche) + nb_feuilles(noeud.droite)
    # on n'ajoute PAS 1 pour les nœuds internes

Recherche dans un arbre quelconque

def est_present(noeud, valeur):
    if noeud is None: return False
    if noeud.valeur == valeur: return True
    return est_present(noeud.gauche, valeur) or \
           est_present(noeud.droite, valeur)
    # Complexité : O(n) — on explore potentiellement tous les nœuds

La propriété ABR

Un ABR vérifie la propriété fondamentale : pour tout nœud,

• toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud
• toutes les valeurs du sous-arbre droit sont strictement supérieures

         8            ← ABR : 3 < 8 < 10
        / \
       3   10
      / \    \
     1   6   14

Vérification : 1 < 3 < 6  ✓   10 < 14  ✓   infixe → 1 3 6 8 10 14 (trié) ✓

Recherche dans un ABR — O(h)

La propriété ABR permet d'éliminer la moitié de l'arbre à chaque étape (comme la dichotomie) :

def recherche_abr(noeud, valeur):
    """Recherche dans un ABR — O(log n) si équilibré, O(n) au pire."""
    if noeud is None: return False      # non trouvé
    if valeur == noeud.valeur: return True  # trouvé !
    elif valeur < noeud.valeur:
        return recherche_abr(noeud.gauche, valeur)  # aller à gauche
    else:
        return recherche_abr(noeud.droite, valeur)  # aller à droite

Insertion dans un ABR

def insertion_abr(noeud, valeur):
    """Insère une valeur dans un ABR. Retourne la nouvelle racine."""
    if noeud is None:
        return Noeud(valeur)              # créer un nouveau nœud feuille
    if valeur < noeud.valeur:
        noeud.gauche = insertion_abr(noeud.gauche, valeur)
    elif valeur > noeud.valeur:
        noeud.droite = insertion_abr(noeud.droite, valeur)
    # si valeur == noeud.valeur : doublon ignoré
    return noeud                          # toujours retourner le nœud

# Exemple : construire un ABR par insertions successives
racine = None
for val in [8, 3, 10, 1, 6, 14]:
    racine = insertion_abr(racine, val)

ABR dégénéré : le pire cas

Si on insère des valeurs dans l'ordre croissant, l'ABR dégénère en liste chaînée :

Insertion : 5, 3, 7, 2, 4, 6, 8
         5
        / \
       3   7
      / \ / \
     2 4 6 8
hauteur = 2
recherche : O(log n)

Insertion : 1, 2, 3, 4, 5
1
 \
  2
   \
    3
     \
      4
       \
        5
hauteur = n-1
recherche : O(n) !

Vérifier qu'un arbre est un ABR

L'approche naïve (vérifier seulement les fils directs) est incorrecte. Il faut propager des bornes min/max :

def est_abr(noeud, mini=None, maxi=None):
    """Vérifie la propriété ABR en propageant les bornes."""
    if noeud is None: return True
    if mini is not None and noeud.valeur <= mini: return False
    if maxi is not None and noeud.valeur >= maxi: return False
    return (est_abr(noeud.gauche, mini, noeud.valeur) and
            est_abr(noeud.droite, noeud.valeur, maxi))

# En propageant : le fils gauche doit avoir val < noeud.valeur
# ET respecter toutes les bornes des ancêtres