Probleme – L'arbre bicolore : d'où vient la garantie, et jusqu'où elle est serrée

1. La minoration du nombre de nœuds. Notons $bh(x)$ la hauteur noire d'un nœud $x$ : le nombre de nœuds noirs sur un chemin de $x$ (exclu) à une feuille vide de son sous-arbre. La contrainte 4 assure que ce nombre ne dépend pas du chemin choisi, donc $bh$ est bien définie.

Affirmation : tout sous-arbre enraciné en $x$ contient au moins $2^{bh(x)}-1$ nœuds internes. Par induction sur la hauteur de $x$.

• Si $x$ est une feuille vide, $bh(x)=0$ et le sous-arbre a $0=2^0-1$ nœud.
• Sinon $x$ a deux fils. Chaque fils $y$ vérifie $bh(y)\ge bh(x)-1$ : il vaut $bh(x)$ si $y$ est rouge, $bh(x)-1$ s'il est noir. Par hypothèse d'induction, chaque sous-arbre fils contient au moins $2^{bh(x)-1}-1$ nœuds, d'où

$$n_x\ge 1+2(2^{bh(x)-1}-1)=2^{bh(x)}-1.$$

Appliqué à la racine, dont la hauteur noire est $b$ : $n\ge 2^b-1$, soit $b\le {\log }_2(n+1)$.

2. La majoration de la hauteur. Sur un chemin de la racine à une feuille vide, la contrainte 3 interdit deux rouges consécutifs, et la contrainte 1 impose une racine noire. Un tel chemin de $\ell$ nœuds contient donc au plus $\lfloor \ell /2\rfloor$ rouges, donc au moins $\lceil \ell /2\rceil$ noirs : $b\ge \lceil \ell /2\rceil \ge \ell /2$, c'est-à-dire $\ell \le 2b$. Comme $h$ est la longueur du plus long chemin,

$$h\le 2b\le 2{\log }_2(n+1).$$

3. La famille extrémale. On construit deux familles d'arbres de hauteur noire $b$ :

$$P_0=\text{vide},P_b=\text{Noir}(P_{b-1},P_{b-1})\text{(parfait, tout noir)},$$

$$E_0=\text{vide},E_b=\text{Noir}(\text{Rouge}(E_{b-1},P_{b-1}),P_{b-1}).$$

$E_b$ vérifie les quatre contraintes : sa racine est noire ; ses nœuds rouges n'ont que des fils noirs par construction ; et tout chemin traverse $b$ nœuds noirs, puisque le rouge n'en compte pas.

Un calcul immédiat donne, avec $h$ la hauteur en arêtes :

$$h(E_b)=2b-1,n(E_b)=n(E_{b-1})+2^b=2^{b+1}-2.$$

Mesuré — les quatre contraintes vérifiées par programme sur chaque arbre :

Le rapport tend vers $1$ : la borne $2{\log }_2(n+1)$ est serrée à une constante additive près — ici $3$ exactement, puisque $2{\log }_2(n+1)-h=2(b+1)-(2b-1)=3$ à la limite. Aucune amélioration du facteur $2$ n'est possible.

Pour comparaison, l'arbre parfait $P_b$ atteint $h/\text{borne}\approx 0,475$ : il est deux fois plus court que la borne, ce qui montre bien que le facteur $2$ mesure un déséquilibre autorisé, non un déséquilibre obligatoire.

4. La conséquence pratique. Un arbre bicolore peut être deux fois plus haut qu'un arbre parfait de même taille, et cette limite est atteinte. Un million de clés : $h\le 40$ contre $19$ pour l'arbre parfait. On paye donc, dans le pire des cas, un facteur $2$ sur chaque recherche — c'est le prix de l'équilibrage approché, et il est bon marché : maintenir un arbre parfaitement équilibré coûterait $\Theta (n)$ par insertion. Le bon compromis n'est pas l'optimum, c'est celui dont le coût de maintien reste du même ordre que le gain.