Comment rechercher une clé dans un arbre binaire de recherche ?
Réponse courte
Compare la clé cherchée à la racine : si elle est égale, la recherche réussit ; si elle est plus petite, poursuis à gauche ; si elle est plus grande, à droite. Atteindre une position vide signifie que la clé est absente.
Comprendre
Suivre un seul chemin
Dans un arbre binaire de recherche (ABR), toutes les clés du sous-arbre gauche d’un nœud sont inférieures à sa clé et celles du sous-arbre droit sont supérieures. Cette règle vaut aussi pour les descendants, pas seulement les enfants immédiats. Elle permet d’écarter tout un sous-arbre à chaque comparaison.
Dérouler la recherche
Commence à la racine. Si la clé cherchée est égale à la clé courante, renvoie vrai. Si elle est plus petite, recommence dans l’enfant gauche ; si elle est plus grande, recommence dans l’enfant droit. Si l’arbre courant est vide, renvoie faux : aucune position restante ne peut contenir la clé. Dans l’arbre de racine 8, avec 3 à gauche, puis 6 à droite de 3, la recherche de 7 suit 8 → 3 → 6 → position droite vide et conclut à l’absence.
Coût dépendant de la forme
La recherche ne parcourt pas forcément tous les nœuds : elle descend le long d’un chemin. Pour une hauteur h mesurée en arêtes, elle examine au plus h + 1 nœuds non vides. Un arbre déséquilibré peut former une chaîne ; sa recherche peut alors être linéaire. Un ABR ne garantit pas à lui seul une hauteur faible.
Étapes
- Place-toi à la racine et compare sa clé avec la clé cherchée.
- Renvoie vrai si elles sont égales ; sinon choisis le sous-arbre gauche ou droit selon l’ordre des clés.
- Répète la comparaison jusqu’à trouver la clé ou atteindre None, qui signifie qu’elle est absente.
Exemples
- Avec la racine 8 et le fils gauche 3, chercher 3 réussit à la première comparaison après le départ : 3 < 8, puis 3 égale la clé de ce nœud.
- Dans l’arbre de racine 8, 3 à gauche et 6 à droite de 3, rechercher 7 descend vers 3, puis 6, puis une position droite vide : 7 est absent.
- Dans un ABR où 8 a 10 à droite, rechercher 14 ne doit jamais partir dans le sous-arbre gauche de 8, puisque toutes ses clés sont inférieures à 8.
Pièges fréquents
- Explorer les deux sous-arbres à chaque étape ignore la propriété d’ordre et transforme la recherche en parcours complet inutile.
- Conclure que la clé est absente après un seul désaccord avec la racine est faux : il faut poursuivre dans le sous-arbre indiqué par la comparaison.
Pourquoi ça marche
L’ordre de l’ABR prouve qu’un côté ne peut contenir la clé ; le jeter sans examen conserve la possibilité d’une recherche complète en ne suivant qu’un chemin.
