Aller au contenu principal

Les Arbres Binaires de Recherche (ABR)

Définition et application​

Définition

Un Arbre Binaire de Recherche (ABR) est un arbre binaire vérifiant pour chaque noeud que :

  • les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du noeud ;
  • les valeurs du sous-arbre droit sont supérieures ou égales à la valeur du noeud.

Cette propriété est récursive : chaque sous-arbre est lui-même un ABR.

Exemple d'ABR​

La racine de cet ABR est 15 :

  • les valeurs du sous-arbre gauche (6, 3, 7) sont inférieures à 15 ;
    • Pour le sous-arbre gauche 6, son sous-arbre gauche 3 est inférieur à 6 et son sous-arbre droit 7 est supérieur à 6.
  • les valeurs du sous-arbre droit (18, 17, 20) sont supérieures à 15 ;
    • Pour le sous-arbre droit 18, son sous-arbre gauche 17 est inférieur à 18 et son sous-arbre droit 20 est supérieur à 18.

Application des ABR​

Les Arbres Binaires de Recherche (ABR) ne sont pas seulement une structure abstraite : ils servent à organiser et rechercher efficacement des données dans de nombreux contextes :

  • Indexation dans les bases de données
    Les ABR (et leurs variantes équilibrées comme les AVL ou Red-Black Trees) sont utilisés pour construire des index permettant de retrouver rapidement des enregistrements selon une clé (par exemple un identifiant ou un prix), ce qui accélère les requêtes.

  • Gestion de tables de symboles
    Dans un compilateur ou un interpréteur, on utilise souvent des ABR pour stocker et retrouver les informations associées aux identifiants (variables, fonctions,...).

  • Organisation de fichiers
    Des concepts dérivés d'ABR sont utilisés pour structurer les répertoires et fichiers afin de permettre une recherche rapide dans un système de fichiers.

  • Tables de routage et réseau
    Les arbres binaires aident à déterminer rapidement les chemins ou règles à appliquer dans des tables de routage.

En résumé : les ABR permettent d'accélérer la recherche, de garder des données triées et d'optimiser des opérations courantes sur des collections d'éléments, ce qui se retrouve partout dans l'informatique moderne.

Méthode sur les ABR​

Recherche​

Avoir un ABR permet de rechercher une valeur dans l'arbre de manière efficace grâce à sa structure ordonnée.
La recherche d'une valeur x dans un ABR ressemble à une recherche dichotomique :

  • On compare la valeur de la racine de l'ABR avec la valeur x cherchée
  • Si les valeurs sont identiques, on retourne True
  • Sinon, si on est sur une feuille, on retourne False
  • Sinon :
    • Si la valeur est inférieure à la racine, cela signifie qu'il faut regarder dans le sous-arbre gauche et on recommence
    • Sinon, on regarde dans le sous-arbre droit et on recommencer l'algorithme.
Complexité

Dans un ABR de n noeuds, la recherche d'une valeur a une complexité de O(log n) (logarithmique), car à chaque comparaison, on élimine la moitié des noeuds restants à explorer.
Dans un arbre binaire, dans le pire des cas, la complexité peut être de O(n) (linéaire) car il faudrait comparer chaque noeud pour touver la valeur recherchée.

Insertion​

Insérer une valeur dans un ABR consiste à trouver la bonne position en respectant l'ordre de l'arbre.
L'insertion d'une valeur x dans un ABR suit la même logique que la recherche :

  • On compare la valeur x à insérer avec la valeur du noeud courant
  • Si x est inférieure à la valeur du noeud, on continue dans le sous-arbre gauche
  • Si x est supérieure à la valeur du noeud, on continue dans le sous-arbre droit
  • Si on atteint une position vide, on crée un nouveau noeud contenant x
  • Si x est déjà présente (cas des ABR sans doublons), on ne fait rien.
Complexité

Dans un ABR de n noeuds, l'insertion d'une valeur a une complexité de O(log n) (logarithmique), car on ne parcourt qu'un seul chemin de la racine vers une feuille.
Dans le pire des cas (arbre très déséquilibré), la complexité peut devenir O(n) (linéaire).

Propriétés sur les ABR​

ABR équilibré​

Un ABR est équilibré si, pour chaque nœud, les hauteurs des sous-arbres gauche et droit sont proches (en pratique, l'écart reste petit).
Un arbre parfaitement équilibré n'est pas obligatoire, mais plus l'arbre est équilibré, plus les opérations sont rapides.

Hauteur d'un ABR​

La hauteur d'un ABR correspond à la longueur du plus long chemin entre la racine et une feuille.

  • Si l'arbre est bien équilibré, la hauteur est de l'ordre de log2(n)
  • Si l'arbre est déséquilibré (par exemple valeurs insérées dans l'ordre croissant), la hauteur peut atteindre n

Comme la recherche, l'insertion et la suppression suivent un chemin de la racine vers une feuille, leur coût dépend directement de cette hauteur.

Parcours​

Il existe plusieurs manières de parcourir un ABR :

  • Préfixe (racine, gauche, droit)
  • Infixe (gauche, racine, droit)
  • Postfixe (gauche, droit, racine)

La propriété essentielle est la suivante : un parcours infixe d'un ABR affiche toujours les valeurs dans l'ordre croissant.

Minimum et maximum​

Dans un ABR :

  • La plus petite valeur se trouve en allant toujours vers le fils gauche
  • La plus grande valeur se trouve en allant toujours vers le fils droit

Ces opérations se font en O(h) où h est la hauteur de l'arbre, donc en O(log n) si l'arbre est équilibré.

Bilan des complexités​

Pour un ABR de n nœuds :

  • Recherche : O(log n) en moyenne, O(n) au pire
  • Insertion : O(log n) en moyenne, O(n) au pire
  • Suppression : O(log n) en moyenne, O(n) au pire

Le pire cas apparaît lorsque l'ABR devient presque linéaire (comparable à une liste chaînée).