Exercice 4 - Hauteur minimale d'un arbre binaire

Un arbre binaire est un arbre dont chaque noeud a $2$ fils. Un arbre vide, donc sans noeud, noté $\emptyset$, est de profondeur $h(\emptyset) = -1$. Un noeud est une feuille si ses deux fils sont des arbres vides. Soit $x$ un noeud, $l$ et $r$ ses fils la hauteur de $x$ est alors $h(x) = 1 + \max(h(l), h(r))$. La hauteur d'un arbre binaire est la hauteur de son noeud de hauteur maximale, donc de la racine. La racine $r$ est de profondeur $p(r) = 0$, tout noeud $x$ de père $y$ est de profondeur $p(x) = p(y) + 1$.

1. Quelle est la hauteur d'une feuille d'un arbre binaire?
2. Comment disposer les noeuds pour que la hauteur d'un arbre binaire à $n$ noeuds soit minimale ?
3. Nous ne considérerons dorénavant que des arbres binaires dans lesquels les noeuds sont disposés comme décrit dans la question précédente. Soit $A$ un arbre de profondeur $h$, déterminer pour tout $k \in \{0, \ldots, h-1\}$ le nombre de noeuds de $A$ dont la profondeur est $k$.
4. Encadrer le nombre de noeuds de profondeur $h$.
5. Donner la borne inférieure du nombre $n$ de noeuds d'un arbre binaire de profondeur $h$.
6. Majorer $h$ en fonction de $n$.
7. Donner une borne asymptotique supérieure de la hauteur $h$ d'un arbre binaire à $n$ noeuds de hauteur minimale.