Sommaire

Arbres binaires de recherche

1. Définition

Dans un arbre binaire de recherche, tous les éléments sont dotés d’une clé et ils sont positionnés dans l’arbre en fonction de cette clé. La clé rend lisible et utilisable l’ordre de l’arbre. La clé est en général un nombre qui est ajouté à l’élément. C’est grâce à ce nombre que l’élément peut être rangé et identifié à une place précise dans l’arbre. Tous les éléments peuvent ensuite être retrouvés rapidement grâce à leur clé, sans être obligés de parcourir tout l’arbre systématiquement. Les éléments rangés dans l’arbre sont en quelque sorte triés en fonction de leur clé. Il est facile d’ajouter des nouveaux éléments ou de supprimer des éléments sans modifier l’ordre de l’arbre.

Les clés obéissent aux règles suivantes :

Pour chaque nœud de l’arbre :

  • les clés du sous-arbre gauche (SAG) sont inférieures à celle de la racine,

  • les clés du sous-arbre droit (SAD) sont supérieures à celle de la racine,

  • toutes les clés sont différentes, il n’y a pas de clé identique.

Par exemple la suite de clés 17, 3, 15, 9, 27, 44, 2, 50, 30 donne l’arbre suivant :

images/06ri68.PNG

L’arbre ...