Au programme de ce chapitre
- I. Définition et propriété fondamentale
- II. Insertion et recherche dans un ABR
- III. Complexité : le rôle décisif de l'équilibrage
- Savoir-faire
- Exercices types corrigés
- Teste-toi — vrai ou faux ?
- Pièges fréquents et astuces
- À retenir
La définition à retenir
Définition Un arbre binaire de recherche (ABR) est un arbre binaire dont chaque nœud contient une clé, avec la propriété suivante : pour tout nœud, toutes les clés de son sous-arbre gauche lui sont strictement inférieures, et toutes les clés de son sous-arbre droit lui sont strictement supérieures.
🔒 Illustration du chapitre completIncluse dans le cours complet, avec la méthode et les exercices corrigés.La voir gratuitement pendant 7 jours
Un exemple corrigé
Exemple Testé avec
python3, en insérant successivement 47, 23, 68, 12, 35, 59, 81, 40 :
>>> class NoeudABR:
... def __init__(self, cle):
... self.cle = cle
... self.gauche = None
... self.droit = None
...
>>> def inserer(racine, cle):
... if racine is None:
... return NoeudABR(cle)
... if cle < racine.cle:
... racine.gauche = inserer(racine.gauche, cle)
... elif cle > racine.cle:
... racine.droit = inserer(racine.droit, cle)
... return racine
...
>>> def parcours_infixe(racine):
... if racine is None:
... return []
... return parcours_infixe(racine.gauche) + [racine.cle] + parcours_infixe(racine.droit)
...
>>> valeurs = [47, 23, 68, 12, 35, 59, 81, 40]
>>> racine = None
>>> for v in valeurs:
... racine = inserer(racine, v)
...
>>> parcours_infixe(racine)
[12, 23, 35, 40, 47, 59, 68, 81]Les erreurs fréquentes à éviter
Piège. La complexité O(log n) n'est atteinte que si l'arbre est équilibré (sinon O(n)).
Attention Un ABR n'équilibre pas automatiquement sa forme : deux ABR contenant exactement les mêmes clés peuvent avoir des hauteurs très différentes selon l'ordre d'insertion. Des structures comme les arbres AVL ou rouge-noir, hors programme, rééquilibrent l'arbre après chaque insertion pour garantir O(log n) dans tous les cas.
L'astuce du prof
Astuce. Parcours infixe d'un ABR = clés triées : un moyen simple de les ordonner.
Exercices corrigés
Cherche d'abord seul, puis ouvre la correction.
Exercice 1
Quelle est la propriété d'ordre d'un ABR ?
Voir la correction
Sous-arbre gauche < nœud < sous-arbre droit.
Exercice 2
Que donne le parcours infixe d'un ABR ?
Voir la correction
Les clés triées par ordre croissant.