Les arbres binaires

Mémo

Vocabulaire

Arbre binaire: Structure hiérarchique où chaque nœud a au plus deux enfants (gauche et droit).
Racine: Nœud au sommet de l'arbre (sans parent).
Feuille: Nœud sans enfant.
Nœud interne: Nœud ayant au moins un enfant.
Hauteur: Longueur du plus long chemin de la racine à une feuille. Un arbre réduit à un nœud a une hauteur de 0. L'arbre vide a une hauteur de $-1$ (par convention).
Taille: Nombre total de nœuds.
Profondeur d'un nœud: Distance (nombre d'arêtes) entre la racine et ce nœud.

Propriétés fondamentales

Pour un arbre binaire de hauteur $h$ et de taille $n$ :

$h + 1 ⩽ n ⩽ 2^{h+1} - 1$ ;
Un arbre complet de hauteur $h$ a exactement $2^{h+1} - 1$ nœuds ;
$\lfloor \log_2(n) \rfloor ⩽ h ⩽ n - 1$.

Arbre binaire de recherche (ABR)

Un ABR est un arbre binaire où, pour chaque nœud :

Toutes les valeurs du sous-arbre gauche sont inférieures ;
Toutes les valeurs du sous-arbre droit sont supérieures.

La recherche, l'insertion et la suppression sont en $O(h)$, soit $O(\log n)$ si l'arbre est équilibré.

Parcours d'un arbre binaire

Préfixe (préordre): Racine, sous-arbre gauche, sous-arbre droit.
Infixe (inordre): Sous-arbre gauche, racine, sous-arbre droit. Pour un ABR, donne les valeurs dans l'ordre croissant.
Suffixe (postordre): Sous-arbre gauche, sous-arbre droit, racine.
En largeur (BFS): Niveau par niveau, de gauche à droite (utilise une file).

Exemples

Implémentation d'un arbre binaire

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

arbre = Arbre(5,
    Arbre(3, Arbre(1), Arbre(4)),
    Arbre(8, None, Arbre(9))
)

(Arbre : voir la version PDF pour la représentation graphique)

Taille et hauteur (récursif)

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

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

Parcours

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

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

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

# Pour l'arbre ci-dessus :
# prefixe donne [5, 3, 1, 4, 8, 9]
# infixe  donne [1, 3, 4, 5, 8, 9]  (ordre croissant car ABR)
# suffixe donne [1, 4, 3, 9, 8, 5]

Parcours en largeur

from collections import deque

def largeur(arbre):
    if arbre is None:
        return []
    file = deque([arbre])
    resultat = []
    while file:
        noeud = file.popleft()
        resultat.append(noeud.valeur)
        if noeud.gauche:
            file.append(noeud.gauche)
        if noeud.droit:
            file.append(noeud.droit)
    return resultat
# largeur donne [5, 3, 8, 1, 4, 9]

Recherche dans un ABR

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

Insertion dans un ABR

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

Exercices

Exercice 1 — Propriétés d'un arbre

3 pts

Soit l'arbre binaire suivant :

(Arbre : voir la version PDF pour la représentation graphique)

Donner la taille, la hauteur et les feuilles de cet arbre.
Est-ce un ABR ? Justifier.
Donner le résultat des quatre parcours (préfixe, infixe, suffixe, largeur).

▶ Voir la solution

Taille : 8 nœuds. Hauteur : 3 (chemin 10-6-3-1). Feuilles : 1, 7, 9, 20.
Oui, c'est un ABR. Pour chaque nœud, les valeurs à gauche sont inférieures et à droite supérieures. Par exemple, 10 a ${1,3,6,7,8,9}$ à gauche et ${15,20}$ à droite.
Parcours :
- Préfixe : 10, 6, 3, 1, 8, 7, 9, 15, 20.
- Infixe : 1, 3, 6, 7, 8, 9, 10, 15, 20 (ordre croissant, confirmation que c'est un ABR).
- Suffixe : 1, 3, 7, 9, 8, 6, 20, 15, 10.
- Largeur : 10, 6, 15, 3, 8, 20, 1, 7, 9.

Exercice 2 — Fonctions récursives

3 pts

Écrire les fonctions suivantes :

nb_feuilles(arbre) qui renvoie le nombre de feuilles.
somme(arbre) qui renvoie la somme de toutes les valeurs.
est_abr(arbre) qui vérifie si un arbre est un ABR.

▶ Voir la solution

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)

def somme(arbre):
    if arbre is None:
        return 0
    return arbre.valeur + somme(arbre.gauche) + somme(arbre.droit)

def est_abr(arbre, mini=float('-inf'), maxi=float('inf')):
    if arbre is None:
        return True
    if arbre.valeur <= mini or arbre.valeur >= maxi:
        return False
    return (est_abr(arbre.gauche, mini, arbre.valeur) and
            est_abr(arbre.droit, arbre.valeur, maxi))

Principe de est_abr : on propage un intervalle $]mini ; maxi[$ que chaque nœud doit respecter :

le sous-arbre gauche doit avoir des valeurs dans $]mini ; valeur[$ ;
le sous-arbre droit dans $]valeur ; maxi[$.

Attention : vérifier uniquement que gauche.valeur < valeur et droit.valeur > valeur ne suffit pas ! Il faut vérifier que tous les nœuds respectent la contrainte.

Exercice 3 — Construction d'un ABR

2 pts

On insère successivement les valeurs 5, 2, 8, 1, 3, 7, 9 dans un ABR initialement vide.

Dessiner l'arbre obtenu.
Quel serait l'arbre si l'on insérait les mêmes valeurs dans l'ordre 1, 2, 3, 5, 7, 8, 9 ? Quel problème cela pose-t-il ?

▶ Voir la solution

1. Insertion de 5, 2, 8, 1, 3, 7, 9 :

(Arbre : voir la version PDF pour la représentation graphique)

Arbre équilibré de hauteur 2. La recherche est en $O(\log n)$.

2. Insertion de 1, 2, 3, 5, 7, 8, 9 :

(Arbre : voir la version PDF pour la représentation graphique)

L'arbre dégénère en une liste chaînée (hauteur $= n - 1 = 6$). La recherche est en $O(n)$, ce qui annule l'avantage de l'ABR.

C'est pourquoi on utilise des arbres équilibrés (AVL, arbres rouge-noir) dans les applications réelles.

← Retour aux fiches