Problème — Combien de nœuds faut-il pour être haut ?

1. La récurrence. Un arbre équilibré de hauteur $h\ge 1$ et de taille minimale a une racine, un fils de hauteur $h-1$ — il en faut un pour atteindre la hauteur $h$ — et un second fils dont la hauteur est au moins $h-2$, par la contrainte d'équilibre. Pour minimiser, on prend exactement $h-2$, et chacun des deux fils est lui-même minimal. D'où

$$N(h)=1+N(h-1)+N(h-2),N(-1)=0,N(0)=1.$$

La convention $h(\text{Vide})=-1$ du cours rend l'initialisation limpide : $N(-1)=0$ est l'arbre vide, et non un cas particulier. Avec la convention $h(\text{Vide})=0$, il faudrait ici une exception.

2. Les valeurs, calculées, et la forme close :

On reconnaît les nombres de Fibonacci diminués de $1$, et l'identité

$$N(h)=F(h+3)-1$$

a été vérifiée pour $h$ de $0$ à $20$, avec $F(1)=F(2)=1$. Par exemple $N(10)=232$ et $F(13)=233$.

Preuve. Par récurrence forte. $N(-1)=0=F(2)-1$ et $N(0)=1=F(3)-1$. Puis

$$N(h)=1+(F(h+2)-1)+(F(h+1)-1)=F(h+2)+F(h+1)-1=F(h+3)-1.$$

3. La majoration de la hauteur. Un arbre équilibré de hauteur $h$ et de taille $n$ vérifie $n\ge N(h)=F(h+3)-1$, donc $n+1\ge F(h+3)$. Comme $F(k)\sim {\phi }^k/\sqrt{5}$ avec $\phi =(1+\sqrt{5})/2$, on obtient en passant au logarithme

$$h\le {\log }_{\phi }(n+2)+O(1)=\frac{{\log }_2(n+2)}{{\log }_2\phi }+O(1)\approx 1,4405{\log }_2(n+2)-0,3277.$$

Cette borne a été vérifiée numériquement pour $h$ de $0$ à $40$, c'est-à-dire jusqu'à $N(40)=433494436$ nœuds : elle tient, avec un écart maximal de $1,96$.

Le chiffre à retenir est $1,44$. Un arbre équilibré en hauteur est au plus $44\%$ plus haut que l'arbre parfait de même taille. La comparaison, obtenue en cherchant le plus grand $h$ tel que $N(h)\le n$, est frappante :

Contre une hauteur de $10^9-1$ pour un peigne de même taille.

4. Pourquoi ce résultat gouverne le chapitre suivant. Le cours a établi deux choses : la hauteur est comprise entre $\Theta (\log n)$ et $n-1$, et toute recherche coûte $O(h)$. Il en découlait une question sans réponse : comment garantir qu'on est du bon côté ?

Ce problème donne la réponse, et elle est du meilleur genre : une contrainte purement locale — en chaque nœud, les hauteurs des fils diffèrent d'au plus $1$ — suffit à garantir une propriété globale, $h=O(\log n)$. On peut donc maintenir l'équilibre en ne regardant, à chaque insertion, que le voisinage du chemin parcouru : c'est ce que feront les arbres bicolores du chapitre chap:tas.

L'arbre qui sature la borne mérite d'être connu : c'est l'arbre de Fibonacci, défini par ${\mathcal{F}}_h=\text{Nœud}({\mathcal{F}}_{h-1},e,{\mathcal{F}}_{h-2})$. Il est le pire cas de tous les algorithmes d'arbres équilibrés, et c'est donc le premier arbre sur lequel on les teste — une application directe de la méthode du chapitre chap:discipline : ne pas tester au hasard, tester aux frontières.