1.1 Arbre Binaire de Recherche (ABR)
Un Arbre Binaire de Recherche est un Arbre Binaire qui respecte une organisation ordonnée particulière.
Les clés des Noeuds doivent toutes pouvoir être comparées entre elles (c'est à dire disposer d'un opérateur < ou > ...).
La définition de l'Arbre Binaire de Recherche (ABR) impose que :
- toutes les clés du sous-arbre gauche soient plus petites* que la clé de la racine de l'Arbre étudié
- toutes les clés du sous-arbre de droite soient plus grandes* que la clé de la racine de l'Arbre étudié
La présence du * indique que l'égalité peut être traitée comme vous le voulez : à vous de choisir si vous voulez placer le cas EGAL à droite ou à gauche. Dans un premier temps, nous nous limiterons au cas des arbres pour lequel les clés sont toutes différentes.
On notera qu'on peut également faire l'inverse : mettre les plus grandes à gauche et les plus petites à droite.
Exemples
Un Arbre Binaire de Recherche parfait :

Les mêmes noeuds avec les mêmes clés dans une configuration moins optimale pour la recherche :

L'intérêt ?
Comme pour la liste-tableau trié qui permet une recherche dichotomique à coût logarithmique plutôt que linéaire, l'ABR permet une recherche à coût logarithmique (sur un Arbre proche d'un Arbre Complet) plutôt que linéaire.