Arbres Binaires de Recherche (ABR)
Les arbres binaires de recherche sont une structure de données fondamentale en informatique. Ils permettent d'effectuer des opérations de recherche, d'insertion et de suppression de manière efficace, avec une complexité moyenne en O(log n).
1. Définition
Un Arbre Binaire de Recherche (ABR) est un arbre binaire qui vérifie la propriété suivante pour tout nœud N :
- Toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur de N
- Toutes les valeurs du sous-arbre droit sont strictement supérieures à la valeur de N
Exemple d'ABR
Cet arbre est un ABR car : - Pour le nœud 8 : tous les nœuds à gauche (3, 1, 6, 4, 7) sont < 8, tous ceux à droite (10, 14, 13) sont > 8 - Pour le nœud 3 : 1 < 3 et 6 > 3 - Et ainsi de suite pour tous les nœuds...
Contre-exemple
Cet arbre n'est pas un ABR car 9 est dans le sous-arbre gauche de 8 alors que 9 > 8.
2. Intérêt des ABR
Pourquoi utiliser un ABR plutôt qu'une liste ?
| Opération | Liste non triée | Liste triée | ABR (équilibré) |
|---|---|---|---|
| Recherche | O(n) | O(log n) | O(log n) |
| Insertion | O(1) | O(n) | O(log n) |
| Suppression | O(n) | O(n) | O(log n) |
L'ABR combine les avantages : - Recherche rapide (comme une liste triée avec dichotomie) - Insertion rapide (pas besoin de décaler des éléments)
3. Implémentation en Python
Nous utilisons une classe Noeud pour représenter chaque nœud de l'arbre :
4. Recherche dans un ABR
Principe
Pour rechercher une valeur v dans un ABR :
1. Si l'arbre est vide → la valeur n'est pas présente
2. Si v == valeur du nœud courant → trouvé !
3. Si v < valeur du nœud courant → chercher dans le sous-arbre gauche
4. Si v > valeur du nœud courant → chercher dans le sous-arbre droit
Algorithme récursif
def rechercher(noeud, valeur):
"""
Recherche une valeur dans un ABR.
Retourne True si trouvée, False sinon.
"""
# Cas de base : arbre vide
if noeud is None:
return False
# Valeur trouvée
if valeur == noeud.valeur:
return True
# Recherche dans le sous-arbre approprié
if valeur < noeud.valeur:
return rechercher(noeud.gauche, valeur)
else:
return rechercher(noeud.droit, valeur)
Exemple de déroulement
Recherche de 7 dans l'ABR :
8 8 > 7 → aller à gauche
/ \
3 10 3 < 7 → aller à droite
/ \
1 6 6 < 7 → aller à droite
/ \
4 7 7 == 7 → TROUVÉ !
Complexité
- Meilleur cas : O(1) — la valeur est à la racine
- Cas moyen (arbre équilibré) : O(log n) — on divise par 2 à chaque étape
- Pire cas (arbre dégénéré/filiforme) : O(n) — l'arbre ressemble à une liste
5. Insertion dans un ABR
Principe
Pour insérer une valeur v dans un ABR :
1. Si l'arbre est vide → créer un nouveau nœud avec v
2. Si v < valeur du nœud courant → insérer dans le sous-arbre gauche
3. Si v > valeur du nœud courant → insérer dans le sous-arbre droit
4. Si v == valeur du nœud courant → ne rien faire (pas de doublons)
Algorithme récursif
def inserer(noeud, valeur):
"""
Insère une valeur dans un ABR.
Retourne la racine de l'arbre (éventuellement modifiée).
"""
# Cas de base : arbre vide, on crée un nouveau nœud
if noeud is None:
return Noeud(valeur)
# Insertion récursive
if valeur < noeud.valeur:
noeud.gauche = inserer(noeud.gauche, valeur)
elif valeur > noeud.valeur:
noeud.droit = inserer(noeud.droit, valeur)
# Si valeur == noeud.valeur, on ne fait rien (pas de doublons)
return noeud
Exemple : construction d'un ABR
Insertion successive de : 8, 3, 10, 1, 6, 14, 4, 7, 13
Étape 1: 8 Étape 2: 8 Étape 3: 8
/ / \
3 3 10
Étape 4: 8 Étape 5: 8 ... Résultat final:
/ \ / \
3 10 3 10 8
/ / \ / \
1 1 6 3 10
/ \ \
1 6 14
/ \ /
4 7 13
Complexité
- Cas moyen : O(log n)
- Pire cas : O(n) — si on insère des valeurs déjà triées, l'arbre devient filiforme
6. Suppression dans un ABR
La suppression est l'opération la plus complexe. Il y a trois cas à considérer :
Cas 1 : Le nœud à supprimer est une feuille
On le supprime simplement.
Cas 2 : Le nœud a un seul enfant
On le remplace par son unique enfant.
Cas 3 : Le nœud a deux enfants
On le remplace par : - Son successeur : le plus petit élément du sous-arbre droit - Ou son prédécesseur : le plus grand élément du sous-arbre gauche
Puis on supprime récursivement ce successeur/prédécesseur.
Supprimer 3 (avec successeur = 4) :
8 8
/ \ / \
3 10 → 4 10
/ \ \ / \ \
1 6 14 1 6 14
/ \ / \ /
4 7 13 7 13
Algorithme récursif
def trouver_min(noeud):
"""Trouve le nœud avec la valeur minimale (le plus à gauche)."""
while noeud.gauche is not None:
noeud = noeud.gauche
return noeud
def supprimer(noeud, valeur):
"""
Supprime une valeur d'un ABR.
Retourne la racine de l'arbre (éventuellement modifiée).
"""
# Cas de base : arbre vide
if noeud is None:
return None
# Recherche du nœud à supprimer
if valeur < noeud.valeur:
noeud.gauche = supprimer(noeud.gauche, valeur)
elif valeur > noeud.valeur:
noeud.droit = supprimer(noeud.droit, valeur)
else:
# Nœud trouvé, on le supprime
# Cas 1 et 2 : 0 ou 1 enfant
if noeud.gauche is None:
return noeud.droit
elif noeud.droit is None:
return noeud.gauche
# Cas 3 : 2 enfants
# On remplace par le successeur (min du sous-arbre droit)
successeur = trouver_min(noeud.droit)
noeud.valeur = successeur.valeur
noeud.droit = supprimer(noeud.droit, successeur.valeur)
return noeud
Complexité
- Cas moyen : O(log n)
- Pire cas : O(n)
7. Parcours infixe et tri
Une propriété remarquable des ABR : le parcours infixe donne les éléments dans l'ordre croissant.
def parcours_infixe(noeud):
"""Affiche les éléments de l'ABR dans l'ordre croissant."""
if noeud is not None:
parcours_infixe(noeud.gauche)
print(noeud.valeur, end=" ")
parcours_infixe(noeud.droit)
Pour l'ABR d'exemple :
8. Vérifier si un arbre est un ABR
Attention : il ne suffit pas de vérifier localement que gauche < noeud < droit. Il faut vérifier que toutes les valeurs du sous-arbre gauche sont inférieures.
def est_ABR(noeud, mini=float('-inf'), maxi=float('inf')):
"""
Vérifie si l'arbre est un ABR valide.
mini et maxi définissent l'intervalle autorisé pour la valeur du nœud.
"""
if noeud is None:
return True
# La valeur doit être dans l'intervalle ]mini, maxi[
if not (mini < noeud.valeur < maxi):
return False
# Vérification récursive avec mise à jour des bornes
return (est_ABR(noeud.gauche, mini, noeud.valeur) and
est_ABR(noeud.droit, noeud.valeur, maxi))
9. Problème des arbres dégénérés
Si on insère des valeurs dans l'ordre croissant (1, 2, 3, 4, 5...), l'ABR devient une liste chaînée :
Dans ce cas, toutes les opérations deviennent en O(n) au lieu de O(log n).
Solution : les arbres équilibrés
Pour garantir O(log n), on utilise des arbres équilibrés : - AVL : après chaque insertion/suppression, on rééquilibre si nécessaire - Arbres rouge-noir : utilisés dans beaucoup de bibliothèques standard
Ces structures sont hors programme en NSI, mais il est important de comprendre pourquoi elles existent.
10. Résumé des complexités
| Opération | ABR équilibré | ABR dégénéré |
|---|---|---|
| Recherche | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Suppression | O(log n) | O(n) |
| Parcours complet | O(n) | O(n) |
11. Exercices
Exercice 1 : Construction d'un ABR
Dessiner l'ABR obtenu après insertion successive des valeurs : 50, 30, 70, 20, 40, 60, 80, 35
Exercice 2 : Recherche
Sur l'ABR de l'exercice 1, combien de comparaisons faut-il pour : - Trouver 35 ? - Constater que 45 n'est pas présent ?
Exercice 3 : Suppression
Sur l'ABR de l'exercice 1, dessiner l'arbre après suppression de : 1. 20 (feuille) 2. 30 (nœud avec 2 enfants)
Exercice 4 : Implémentation
Compléter la classe suivante avec les méthodes manquantes :
class ABR:
def __init__(self):
self.racine = None
def inserer(self, valeur):
"""Insère une valeur dans l'ABR."""
pass
def rechercher(self, valeur):
"""Retourne True si valeur est dans l'ABR."""
pass
def supprimer(self, valeur):
"""Supprime une valeur de l'ABR."""
pass
def afficher_trie(self):
"""Affiche toutes les valeurs dans l'ordre croissant."""
pass
Exercice 5 : Analyse
On insère n valeurs aléatoires dans un ABR initialement vide. 1. Quelle est la hauteur moyenne de l'arbre obtenu ? 2. Que se passe-t-il si les valeurs sont insérées dans l'ordre croissant ?
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.