Pourquoi la hauteur d’un arbre binaire de recherche détermine-t-elle le coût de recherche ?

Réponse courte

Une recherche dans un ABR suit un seul chemin de la racine vers un nœud ou une position vide. Sa longueur est bornée par la hauteur : un arbre bas demande peu de comparaisons, tandis qu’une chaîne peut demander presque une par nœud.

Comprendre

La hauteur borne le chemin

À chaque nœud, la comparaison élimine l’un des deux sous-arbres et la recherche descend dans l’autre. Elle ne revient pas en arrière. Avec une hauteur h comptée en arêtes, le chemin maximal rencontre au plus h + 1 nœuds non vides ; le nombre de comparaisons est donc proportionnel à cette hauteur.

Même clés, coûts différents

Un ABR de trois clés 1, 2 et 3 peut avoir 2 comme racine, avec 1 à gauche et 3 à droite : la hauteur vaut 1. La recherche de 3 demande deux comparaisons. Avec les mêmes clés insérées dans l’ordre 1, 2, 3, l’arbre peut devenir une chaîne 1 → 2 → 3, de hauteur 2 ; chercher 3 demande alors trois comparaisons.

Ne pas supposer l’équilibre

Dans un arbre équilibré, la hauteur croît comme le logarithme du nombre de nœuds, donc la recherche est logarithmique. Mais un ABR ordinaire n’est pas nécessairement équilibré. Une suite de clés déjà triée peut produire une chaîne et un coût linéaire au pire. La propriété d’ordre accélère en écartant un côté, mais seule une forme peu haute garantit un chemin court.

Exemples

  • Dans l’arbre de racine 2 avec 1 et 3 comme enfants, rechercher 3 effectue deux comparaisons ; la hauteur est 1 arête.
  • Dans la chaîne 1 puis 2 puis 3 vers la droite, rechercher 3 peut effectuer trois comparaisons ; sa hauteur est 2 arêtes.
  • Pour un arbre de hauteur h, une recherche infructueuse peut aussi descendre jusqu’à la position vide après au plus h + 1 nœuds non vides.

Pièges fréquents

  • Dire que toute recherche dans un ABR est logarithmique confond un arbre quelconque avec un arbre équilibré.
  • Compter seulement les comparaisons réussies oublie qu’une clé absente peut forcer la descente jusqu’à une position vide.

Pourquoi ça marche

Chaque comparaison ne conserve qu’un sous-arbre ; le nombre de comparaisons suit donc le nombre de niveaux rencontrés sur le chemin, qui est limité par la hauteur.

Et maintenant ?

Questions proches

← Toutes les questions-réponses