Chapitre 5 - Partie 3 : Arbres binaires de recherche et parcours

Programme officiel (B.O.)

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.	Calculer la taille et la hauteur d'un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d'abord). Rechercher une clé dans un arbre de recherche, insérer une clé.	Une structure de données récursive adaptée est utilisée. L'exemple des arbres permet d'illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.

---

1. Rappels sur les arbres binaires

1.1 Définition récursive

Un arbre binaire est soit :

• l'arbre vide (noté None en Python) ;
• un nœud contenant une valeur (appelée étiquette ou clé), un sous-arbre gauche et un sous-arbre droit, qui sont eux-mêmes des arbres binaires.

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

1.2 Vocabulaire

Terme	Définition
Racine	Nœud au sommet de l'arbre (ici : 8)
Feuille	Nœud sans enfants (ici : 1, 4, 7, 13)
Nœud interne	Nœud ayant au moins un enfant
Sous-arbre gauche/droit	Arbre formé par l'enfant gauche/droit et ses descendants
Taille	Nombre total de nœuds
Hauteur	Longueur du plus long chemin de la racine à une feuille
Profondeur d'un nœud	Nombre d'arêtes entre la racine et ce nœud

1.3 Implémentation en Python (classe)

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

Construction de l'arbre de l'exemple :

arbre = Noeud(8,
    Noeud(3,
        Noeud(1),
        Noeud(6, Noeud(4), Noeud(7))
    ),
    Noeud(10,
        None,
        Noeud(14, Noeud(13), None)
    )
)

---

2. Taille et hauteur

2.1 Taille (nombre de nœuds)

La taille est définie récursivement :

$\text{taille}(a) = \begin{cases} 0 & \text{si } a \text{ est vide} \\ 1 + \text{taille}(\text{gauche}) + \text{taille}(\text{droit}) & \text{sinon} \end{cases}$

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

>>> taille(arbre)
9

2.2 Hauteur

La hauteur est la profondeur maximale. Par convention, l'arbre vide a une hauteur de -1 (ou 0 selon les conventions).

$\text{hauteur}(a) = \begin{cases} -1 & \text{si } a \text{ est vide} \\ 1 + \max(\text{hauteur}(\text{gauche}), \text{hauteur}(\text{droit})) & \text{sinon} \end{cases}$

def hauteur(arbre):
    if arbre is None:
        return -1
    return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))

>>> hauteur(arbre)
3

2.3 Encadrement de la hauteur

Pour un arbre binaire de taille n :

$\lfloor \log_2(n) \rfloor \leq h \leq n - 1$

• Hauteur minimale (arbre complet/équilibré) : $h = \lfloor \log_2(n) \rfloor$
• Hauteur maximale (arbre filiforme, dégénéré en liste) : $h = n - 1$

2.4 Compter les feuilles

def nb_feuilles(arbre):
    if arbre is None:
        return 0
    if arbre.gauche is None and arbre.droit is None:
        return 1
    return nb_feuilles(arbre.gauche) + nb_feuilles(arbre.droit)

---

3. Parcours en profondeur

Les parcours en profondeur (Depth-First Search, DFS) explorent l'arbre en descendant le plus profondément possible avant de remonter. Ils diffèrent par le moment où l'on traite la racine.

3.1 Parcours préfixe (racine - gauche - droite)

On traite la racine d'abord, puis le sous-arbre gauche, puis le sous-arbre droit.

def parcours_prefixe(arbre):
    if arbre is None:
        return []
    return ([arbre.valeur]
            + parcours_prefixe(arbre.gauche)
            + parcours_prefixe(arbre.droit))

Sur notre exemple : 8, 3, 1, 6, 4, 7, 10, 14, 13

3.2 Parcours infixe (gauche - racine - droite)

On traite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.

def parcours_infixe(arbre):
    if arbre is None:
        return []
    return (parcours_infixe(arbre.gauche)
            + [arbre.valeur]
            + parcours_infixe(arbre.droit))

Sur notre exemple : 1, 3, 4, 6, 7, 8, 10, 13, 14

Propriété remarquable

Pour un arbre binaire de recherche, le parcours infixe donne les valeurs dans l'ordre croissant.

3.3 Parcours suffixe (gauche - droite - racine)

On traite les sous-arbres d'abord, puis la racine en dernier.

def parcours_suffixe(arbre):
    if arbre is None:
        return []
    return (parcours_suffixe(arbre.gauche)
            + parcours_suffixe(arbre.droit)
            + [arbre.valeur])

Sur notre exemple : 1, 4, 7, 6, 3, 13, 14, 10, 8

3.4 Résumé des parcours en profondeur

Parcours	Ordre	Résultat sur l'exemple
Préfixe	Racine → Gauche → Droit	8, 3, 1, 6, 4, 7, 10, 14, 13
Infixe	Gauche → Racine → Droit	1, 3, 4, 6, 7, 8, 10, 13, 14
Suffixe	Gauche → Droit → Racine	1, 4, 7, 6, 3, 13, 14, 10, 8

---

4. Parcours en largeur

4.1 Principe

Le parcours en largeur (Breadth-First Search, BFS) explore l'arbre niveau par niveau, de gauche à droite. Il utilise une file (FIFO).

4.2 Algorithme

from collections import deque

def parcours_largeur(arbre):
    if arbre is None:
        return []
    resultat = []
    file = deque([arbre])
    while file:
        noeud = file.popleft()
        resultat.append(noeud.valeur)
        if noeud.gauche is not None:
            file.append(noeud.gauche)
        if noeud.droit is not None:
            file.append(noeud.droit)
    return resultat

Sur notre exemple : 8, 3, 10, 1, 6, 14, 4, 7, 13

---

5. Arbres binaires de recherche (ABR)

5.1 Définition

Un arbre binaire de recherche (ABR) est un arbre binaire vérifiant pour chaque nœud :

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

5.2 Recherche dans un ABR

La recherche se fait par dichotomie : à chaque nœud, on choisit de descendre à gauche ou à droite.

def recherche_abr(arbre, cle):
    if arbre is None:
        return False
    if cle == arbre.valeur:
        return True
    elif cle < arbre.valeur:
        return recherche_abr(arbre.gauche, cle)
    else:
        return recherche_abr(arbre.droit, cle)

Complexité : dans un ABR équilibré, la recherche est en O(log₂ n) (on divise l'espace de recherche par 2 à chaque étape). Dans le pire cas (arbre dégénéré), elle est en O(n).

5.3 Insertion dans un ABR

Pour insérer une valeur, on descend dans l'arbre comme pour une recherche, puis on crée un nouveau nœud à l'emplacement vide trouvé.

def inserer_abr(arbre, cle):
    if arbre is None:
        return Noeud(cle)
    if cle < arbre.valeur:
        arbre.gauche = inserer_abr(arbre.gauche, cle)
    elif cle > arbre.valeur:
        arbre.droit = inserer_abr(arbre.droit, cle)
    return arbre

# Construction d'un ABR par insertions successives
racine = None
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    racine = inserer_abr(racine, val)

---

Arbre binaire de recherche interactif : activez JavaScript pour utiliser cette visualisation.

À retenir

Concept	Description
Arbre binaire	Structure récursive : vide ou nœud + sous-arbre gauche + sous-arbre droit
Taille	Nombre de nœuds (récursif : 1 + taille gauche + taille droit)
Hauteur	Profondeur maximale (récursif : 1 + max des hauteurs)
Parcours préfixe	Racine → Gauche → Droit
Parcours infixe	Gauche → Racine → Droit (donne l'ordre croissant dans un ABR)
Parcours suffixe	Gauche → Droit → Racine
Parcours en largeur	Niveau par niveau, avec une file
ABR	Arbre binaire de recherche : gauche < racine < droit
Recherche ABR	O(log₂ n) si l'arbre est équilibré