L'arbre binaire de recherche (ABR)

La propriété clé de l'ABR

Un arbre binaire de recherche (ABR) est un arbre binaire qui respecte une règle stricte à chaque noeud : toutes les valeurs de son sous-arbre gauche lui sont inférieures, et toutes les valeurs de son sous-arbre droit lui sont supérieures. Cette règle s'applique à tous les noeuds de l'arbre, pas seulement à la racine.

Un gros exemple complet

                    8
                  /   \
                 3     10
                / \       \
               1   6        14
                  / \      /
                 4   7    13

Vérifions la règle sur quelques noeuds :

• racine 8 : sous-arbre gauche (3, 1, 6, 4, 7) tous < 8 ; sous-arbre droit (10, 14, 13) tous > 8. (correct)
• noeud 6 : sous-arbre gauche (4) < 6 ; sous-arbre droit (7) > 6. (correct)
• noeud 14 : sous-arbre gauche (13) < 14 ; pas de sous-arbre droit. (correct)

Pourquoi cette structure est utile

Grâce à cette règle, chercher une valeur revient à choisir à chaque noeud « je vais à gauche ou à droite ? », exactement comme une recherche par dichotomie. Dans un arbre bien équilibré de n valeurs, une recherche ne coûte que de l'ordre de log2(n) comparaisons, au lieu de n comparaisons dans une liste non triée.

Le parcours infixe retrouve l'ordre trié

Propriété remarquable : si tu lis un ABR en parcours infixe (gauche, racine, droite), tu obtiens toujours les valeurs triées par ordre croissant. Sur l'arbre ci-dessus : 1, 3, 4, 6, 7, 8, 10, 13, 14.

Piège classique

Une erreur fréquente est de ne vérifier la règle « gauche < noeud < droit » qu'au niveau de la racine. La règle doit être respectée à chaque noeud, sur tout son sous-arbre, pas seulement avec son enfant direct : un noeud très à droite dans le sous-arbre gauche de la racine doit quand même rester inférieur à la racine.