Algorithmique et arbres

Ce TP porte sur les arbres rouge-noir, une structure de données particulière utilisée en algorithmique pour maintenir un arbre binaire de recherche équilibré. Il permet de comprendre les propriétés fondamentales des arbres rouge-noir, de vérifier si un arbre donné respecte ces propriétés, et de démontrer que la hauteur d’un arbre rouge-noir est logarithmique en fonction du nombre de nœuds. Pour réaliser ce TP, il faut connaître les bases des arbres binaires de recherche et comprendre la notion de hauteur d’un arbre.

Objectifs

• Identifier si un arbre binaire est un arbre rouge-noir.
• Colorier un arbre binaire de recherche pour en faire un arbre rouge-noir.
• Calculer la hauteur noire d’un nœud dans un arbre rouge-noir.
• Montrer que la hauteur d’un arbre rouge-noir est bornée par 2 log(n + 1), où n est le nombre de nœuds internes.

Prérequis et installation

• Connaissance des arbres binaires de recherche (ABR).
• Notions d’algorithmique de base et de structures de données.
• Compréhension de la notion de hauteur d’un arbre.
• Pas de matériel ou logiciel spécifique requis, ce TP est théorique et s’appuie sur l’analyse d’arbres donnés.

Étape 1 : Vérification des propriétés d’un arbre rouge-noir

Dans cette étape, vous devez examiner les arbres présentés en figure 1 et déterminer s’ils sont des arbres rouge-noir. Un arbre rouge-noir est un arbre binaire de recherche avec un champ supplémentaire par nœud : sa couleur, qui peut être ROUGE ou NOIR. Il doit satisfaire les propriétés suivantes :

• Chaque nœud est soit rouge, soit noir.
• Chaque feuille (nœud NULL) est noire.
• Si un nœud est rouge, alors ses deux fils sont noirs.
• Pour chaque nœud, tous les chemins descendants vers des feuilles contiennent le même nombre de nœuds noirs.
• La racine est noire.

Vérifiez chaque arbre en appliquant ces règles :

• Pour l’arbre (a), la racine n’est pas noire, donc ce n’est pas un arbre rouge-noir.
• Pour l’arbre (b), les chemins vers les feuilles ne contiennent pas le même nombre de nœuds noirs.
• Pour l’arbre (c), ce n’est pas un arbre binaire de recherche, donc il ne peut pas être rouge-noir.
• Pour l’arbre (d), un nœud rouge a un fils rouge, ce qui viole la propriété 3.

Un résultat correct est de constater qu’aucun des arbres proposés n’est un arbre rouge-noir valide.

Étape 2 : Colorier un arbre binaire de recherche pour en faire un arbre rouge-noir

On vous donne un arbre binaire de recherche (figure 2) non colorié. Votre tâche est de colorier chaque nœud en rouge ou noir pour obtenir un arbre rouge-noir valide. Pour cela :

• Assurez-vous que la racine est noire.
• Coloriez les feuilles (nœuds NULL) en noir.
• Respectez la propriété que si un nœud est rouge, ses deux fils sont noirs.
• Vérifiez que tous les chemins descendants vers les feuilles contiennent le même nombre de nœuds noirs.

Par exemple, la figure 3 montre un coloriage correct de l’arbre donné en figure 2. Ce coloriage respecte toutes les propriétés d’un arbre rouge-noir.

Étape 3 : Calcul de la hauteur noire et démonstration de la hauteur logarithmique

Cette étape vise à comprendre et démontrer que la hauteur d’un arbre rouge-noir est bornée par 2 log(n + 1), où n est le nombre de nœuds internes. Pour cela :

Calcul de la hauteur noire Hn(x)

La hauteur noire Hn(x) d’un nœud x est définie comme le nombre de nœuds noirs sur un chemin descendant de x vers une feuille, sans inclure x lui-même.

Dans l’arbre rouge-noir donné (figure 2), calculez :

• Hn(30) = 3
• Hn(20) = 3
• Hn(35) = 2
• Hn(50) = 1

Démonstration par induction

Montrer que le sous-arbre enraciné en un nœud x contient au moins 2^Hn(x) − 1 nœuds internes :

Si la hauteur de x est 0 (x est une feuille), alors le sous-arbre contient 0 nœud interne,
soit 2^0 − 1 = 0.

Si la hauteur de x est h(x) > 0, alors x a deux fils g et d.
On a Hn(g) ≥ Hn(x) − 1 et Hn(d) ≥ Hn(x) − 1.
Par hypothèse d’induction, les sous-arres enracinés en g et d ont chacun au moins
2^Hn(g) − 1 ≥ 2^(Hn(x)−1) − 1 nœuds internes.
Le sous-arbre enraciné en x contient donc au moins :
2 × (2^(Hn(x)−1) − 1) + 1 = 2^Hn(x) − 1 nœuds internes.

Conséquence sur la hauteur de l’arbre

Soit h la hauteur de l’arbre. D’après la propriété 3, au moins la moitié des nœuds sur un chemin de la racine à une feuille sont noirs. Donc :

Hn(racine) ≥ h/2

On en déduit :

n ≥ 2^(h/2) − 1

d’où :

h ≤ 2 log(n + 1)

Résultats attendus

• Reconnaissance correcte qu’aucun arbre de la figure 1 n’est un arbre rouge-noir valide.
• Coloriage correct de l’arbre de la figure 2 en respectant les propriétés rouge-noir (figure 3).
• Calcul exact des hauteurs noires Hn(30) = 3, Hn(20) = 3, Hn(35) = 2, Hn(50) = 1.
• Preuve que le nombre de nœuds internes d’un sous-arbre enraciné en x est au moins 2^Hn(x) − 1.
• Conclusion que la hauteur h de l’arbre est au plus égale à 2 log(n + 1).

Pièges courants

• Confondre les feuilles NULL (toujours noires) avec des nœuds internes.
• Ne pas vérifier que la racine est noire.
• Oublier la propriété que si un nœud est rouge, ses deux fils doivent être noirs.
• Ne pas vérifier que tous les chemins vers les feuilles ont le même nombre de nœuds noirs.
• Dans la démonstration, ne pas appliquer correctement l’hypothèse d’induction sur les fils.
• Confondre hauteur noire et hauteur classique de l’arbre.