Mesures (Bac 🎯)

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

• le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
• le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
• l'article sur les arbres en NSI de Sébastien Hoarau
• le cours de mon collègue Pierre Duclosson
• les cours de Gilles Lassus, de Franck Chambon et de Julien de Villèle sur son site Progalgo.

🔖 Synthèse de ce qu'il faut retenir pour le bac

Arbre binaire et liste chaînée

Point de cours 3

Un arbre binaire dont tous les noeuds internes ont un seul fils (non vide) est un arbre binaire dégénéré : il possède une unique feuille.

Un arbre binaire dégénéré peut être assimilé à une liste chaînée.

Un arbre binaire dégénéré dont tous les fils non vides sont du même côté est un arbre peigne.

Taille et hauteur d'un arbre binaire

Point de cours 4

• La taille d'un arbre binaire est son nombre de noeuds.
• Dans un arbre binaire, il existe une unique chaîne, appelée chemin simple, reliant par des liens de filiation, le noeud racine à un autre noeud. Par la suite, on désigne par arête un lien de filiation entre deux noeuds.
  • La profondeur d'un noeud est le nombre d'arêtes dans le chemin simple reliant la racine à ce noeud.
  • Un niveau dans un arbre binaire est l'ensemble des noeuds de même profondeur.

  • La hauteur d'un arbre binaire peut se définir comme le nombre de noeuds ou comme le nombre d'arêtes dans le plus long chemin simple reliant la racine à une feuille.¹ C'est une mesure importante car elle représente le plus long chemin pour accéder à un élément depuis la racine. Nous privilégierons la définition suivante :

    Définition choisie pour la hauteur d'un arbre binaire

    La hauteur d'un arbre binaire est le nombre de noeuds dans le plus long chemin simple reliant la racine à une feuille. Ainsi un arbre vide a pour hauteur 0.

Définition	Hauteur de l'arbre avec un noeud	Hauteur de l'arbre vide
Par le nombre d'arêtes	0	\(-1\)
Par le nombre de noeuds	1	\(0\)

Exercice 3

💻 Saisir ses réponses sur Capytale

énoncésolution

1. Soit \(n\) un entier strictement positif. Quelle est la hauteur maximale d'un arbre de taille \(n\) ? Quelle est la nature d'un arbre de hauteur maximale pour une taille fixée ?
2. Représenter un arbre de taille \(7\) de hauteur maximale puis un arbre de taille \(7\) et de hauteur minimale.
3. Quelles sont les tailles d'arbre pour lesquelles on aura la même hauteur minimale que pour un arbre de taille \(7\) ?

1. Dans un arbre de taille \(n\), le nombre de noeuds pour un chemin simple reliant la racine à une feuille est inférieur ou égal à \(n\). Il peut être égal à \(n\) si l'arbre est dégénéré et constitue une liste chaînée.
2. Un arbre de taille \(7\) de hauteur maximale (arbre peigne à gauche mais tout arbre dégénéré de taille 7 convient) puis un arbre de taille \(7\) et de hauteur minimale (arbre parfait de hauteur 3) :

1. Les arbres presque complets à gauche avec trois niveaux sont de hauteur \(3\) comme un arbre parfait de taille \(7\). Les tailles de ces arbres sont comprises entre \(2^{3-1}=4\) compris et \(2^{3}-1=7\).

Point de cours 5

• Un arbre binaire parfait est un arbre binaire dans lequel toutes les feuilles sont à la même profondeur c'est-à-dire que tous les niveaux sont remplis complètement.

Un arbre binaire parfait de taille 14 et de hauteur 4

• Un arbre binaire presque complet à gauche est un arbre binaire dans lequel tous les niveaux sont remplis complètement sauf le plus profond où les feuilles sont serrées à gauche.

Un arbre binaire presque complet à gauche de hauteur 4

Point de cours 6

Soit un arbre binaire de taille \(n\) et de hauteur \(h\) (définition avec le nombre de noeuds). On a les encadrements :

Encadrement de la taille d'un arbre binaire

\[h \leqslant n \leqslant 2^{h}-1 < 2^{h}\]

Encadrement de la hauteur d'un arbre binaire

\[\log_{2}(n)< h \leqslant n\]

Un arbre binaire de taille \(n\) est :

• de hauteur maximale si c'est un arbre binaire dégénéré et en particulier si c'est un arbre peigne
• de hauteur minimale si c'est un arbre binaire presque complet à gauche ou si c'est un arbre binaire parfait. Dans ce cas on a \(h=\lfloor \log_{2}(n) \rfloor + 1\) qui est exactement le nombre de chiffres en base \(2\) de \(n\).

Preuve

Je reprends la preuve et le graphique de Julien de Villèle sur son site Progalgo.

Démontrons l'encadrement \(h \leqslant n < 2^{h}\).

• On démontre d'abord l'inégalité \(h \leqslant n\).

  L'inégalité \(h \leqslant n\) est immédiate puisque nous avons choisi de définir la hauteur comme le nombre de noeuds dans un plus long chemin entre la racine et une feuille de l'arbre, elle est donc nécessairement inférieure ou égale au nombre total de noeuds dans l'arbre c'est-à-dire à sa taille. L'égalité est réalisée dans le cas extrême d'un arbre binaire dégénéré qui peut être assimilé à une liste chaînée. Dans ce cas on a bien \(n=h\).

• On démontre ensuite l'inégalité \( n < 2^{h}\).

  Si on numérote tous les noeuds à partir de \(1\) en parcourant l'arbre en largeur de gauche à droite depuis le premier niveau en descendant jusqu'au dernier, on obtient une situation similaire à celle du graphique ci-dessus. On peut remarquer qu'à chaque changement de niveau on ajoute à droite un bit : un \(0\) si le noeud est un fils gauche ou un \(1\) si c'est un fils droit. Ainsi le numéro d'un noeud s'écrit sur au plus \(h\) bits. Le nombre total de noeuds \(n\) est donc inférieur ou égal au plus grand entier qui s'écrit sur \(h\) bits, c'est-à-dire que \(n \leqslant 2^{h}-1<2^{h}\). On peut remarquer que le nombre de noeuds d'un arbre parfait de hauteur \(h\) est exactement le nombre d'entiers qu'on peut écrire sur \(h\) bits c'est-à-dire \(2^{h}-1\). Dans ce cas on a \(2^{h-1} \leqslant n < 2^{h}\) qui équivaut à \(h-1 \leqslant \log_{2}(n) < h\). Comme \(h\) est un entier, cette dernière inégalité équivaut à \(h=\lfloor \log_{2}(n) \rfloor + 1\).

L'inégalité \(\log_{2}(n)< h\) se déduit immédiatement de \(n < 2^{h}\) en appliquant aux deux membres de l'inégalité la fonction logarithme binaire \(\log_{2}\) qui est strictement croissante. En combinant avec \(h \leqslant n\), on en déduit le second encadrement : \(\log_{2}(n)< h \leqslant n\).

Hauteur d'un arbre et complexité des algorithmes sur les arbres binaires

Si on doit stocker \(n\) éléments dans un arbre binaire, la propriété précédente nous permet d'estimer la hauteur de l'arbre c'est-à-dire la longueur du chemin le plus long pour accéder à un élément depuis la racine :

• Dans le meilleur des cas, si on peut construire un arbre parfait ou presque complet à gauche, on aura une hauteur d'arbre \(h\) de l'ordre de \(\log_{2}(n)\) c'est-à-dire du nombre de chiffres en base \(2\) de \(n\). Pour l'accès à l'élément le plus éloigné de la racine, cela représente une complexité logarithmique par rapport à la taille de l'arbre. C'est bien meilleur que pour une liste chaînée (complexité linéaire) !
• Dans le pire des cas, si on construit un arbre peigne ou dégénéré on se retrouve dans une situation équivalente à une liste chaînée avec une complexité linéaire pour accéder à l'élément le plus éloigné de la racine.

Dans un chapitre ultérieur, nous verrons comment, en suivant les liens de filiation depuis la racine, on peut accéder à un élément précis stocké dans un arbre binaire. Pour celà, l'arbre devra vérifier des propriétés d'ordre qui en font un arbre binaire de recherche. Si la hauteur de l'arbre est de l'ordre \(\log_{2}(n)\), on obtiendra alors un algorithme de recherche d'élément de complexité équivalente à celle de la recherche dichotomique dans un tableau trié.

---

1. La hauteur ne diffère que de \(1\) entre les deux définitions, au Bac, la définition utilisée est toujours précisée dans le sujet. ↩