Quelle est la différence entre la taille et la hauteur d’un arbre binaire ?

Réponse courte

La taille compte tous les nœuds de l’arbre. La hauteur mesure la profondeur maximale : avec la convention en arêtes, c’est le nombre d’arêtes du plus long chemin depuis la racine jusqu’à une feuille.

Comprendre

Deux mesures différentes

La taille est un dénombrement de nœuds, quelle que soit leur position. La hauteur décrit l’étendue du plus long chemin descendant depuis la racine. Dans la convention utilisée ici, on compte les arêtes de ce chemin : la racine a une profondeur 0 et un arbre réduit à sa racine a une hauteur 0. D’autres textes comptent plutôt les niveaux ; il faut donc préciser la convention avant de comparer des résultats.

Un exemple pour les distinguer

Considère une racine A avec deux enfants B et C, puis deux enfants D et E sous B. Les nœuds sont A, B, C, D et E : la taille vaut 5. Le chemin A-B-D comporte deux arêtes et c’est le plus long ; la hauteur vaut donc 2. Ajouter un enfant à C ferait passer la taille à 6, sans modifier la hauteur 2. À l’inverse, prolonger une branche peut augmenter la hauteur même si l’autre côté reste vide.

Ce que ces nombres disent

Deux arbres de même taille peuvent avoir des hauteurs différentes. Cinq nœuds peuvent former une chaîne de hauteur 4 ou être répartis plus près de la racine. La taille ne donne donc pas à elle seule la hauteur. Ne compte pas la longueur dessinée des traits : seule la succession des liens parent-enfant intervient.

Exemples

  • A avec enfants B et C, et B avec enfants D et E : taille 5, hauteur 2 arêtes.
  • Une chaîne A-B-C-D-E contient 5 nœuds et a une hauteur 4 arêtes.

Pièges fréquents

  • Confondre hauteur et nombre total de nœuds : la taille vaut 5 dans les deux exemples, mais leurs hauteurs diffèrent.
  • Compter les nœuds du chemin au lieu des arêtes : avec la convention en arêtes, A-B-D donne une hauteur de 2, pas 3.

Et maintenant ?

Questions proches

← Toutes les questions-réponses