Arbres rouges et noirs

Ce TP fait suite à la partie « Arbres binaires en C » des TP sur les arbres, dont on reprend le type et la fonction cree_feuille, et met en œuvre les arbres rouges et noirs du cours sur les arbres.

Rappels

On utilise ici les arbres rouges et noirs obtenus en codant les arbres 2-3 comme dans le cours : un nœud ternaire \((a, b)\) devient un nœud noir \(a\) dont le fils droit \(b\) est rouge. Ainsi :

• la racine est noire, et l'arbre vide est considéré comme noir ;
• un nœud rouge n'a jamais de fils rouge ;
• le fils gauche d'un nœud n'est jamais rouge (les liens rouges penchent à droite) ;
• tous les chemins de la racine à l'arbre vide contiennent le même nombre de nœuds noirs.

Les trois opérations de rééquilibrage sont :

• la rotation droite d'un nœud \(x\) de fils gauche \(y\) : \(y\) prend la place et la couleur de \(x\), et \(x\), devenu fils droit de \(y\), est colorié en rouge ; le fils droit de \(y\) devient le fils gauche de \(x\) ;
• la rotation gauche, symétrique ;
• la bascule d'un nœud dont les deux fils sont rouges : les fils deviennent noirs et le nœud devient rouge, ce qui fait remonter le défaut vers la racine (c'est l'éclatement d'un nœud quaternaire de l'arbre 2-3).

Ces opérations préservent la propriété d'arbre binaire de recherche et le nombre de nœuds noirs sur chaque chemin.

On va rajouter un champ au type précédent pour indiquer la couleur d'un nœud :

struct noeud {
    struct noeud *gauche;
    struct noeud *droite;
    bool rouge;
    int valeur;
};
typedef struct noeud *arbre;

On vous conseille ici de copier le fichier précédent et de faire un nouveau programme.

Question 1

Reprendre cree_feuille pour que les feuilles soient rouges par défaut.

Corrigé

arbre cree_noeud(int x)
{
    arbre n = malloc(sizeof(struct noeud));
    n->valeur = x;
    n->rouge = true;
    n->gauche = n->droite = NULL;
    return n;
}

Un nouveau nœud est rouge : l'insérer ne change pas le nombre de nœuds noirs sur les chemins.

Question 2

Écrire des fonctions arbre rotation_droite(arbre a), arbre rotation_gauche(arbre a) et arbre bascule(arbre a) qui effectuent une des trois opérations en renvoyant la nouvelle racine.

Corrigé

arbre rotation_droite(arbre x)
{
    arbre y = x->gauche;
    x->gauche = y->droite;
    y->droite = x;
    y->rouge = x->rouge;
    x->rouge = true;
    return y;
}

arbre rotation_gauche(arbre y)
{
    arbre x = y->droite;
    y->droite = x->gauche;
    x->gauche = y;
    x->rouge = y->rouge;
    y->rouge = true;
    return x;
}

arbre bascule(arbre a)
{
    a->rouge = true;
    a->gauche->rouge = false;
    a->droite->rouge = false;
    return a;
}

Question 3

Écrire des fonctions utilitaires bool rouge(arbre a) et bool noir(arbre a) qui testent la couleur de la racine. On fera attention au fait que l'arbre vide est noir.

Corrigé

bool rouge(arbre a)
{
    if (a == NULL) return false;
    return a->rouge;
}

bool noir(arbre a)
{
    return !rouge(a);
}

Question 4

Écrire des fonctions arbre essai_rotgauche(arbre a), essai_rotdroite et essai_bascule qui n'effectuent ces opérations que dans les cas nécessaires pour l'insertion.

Corrigé

arbre essai_bascule(arbre a)
{
    if(rouge(a->gauche) && rouge(a->droite))
        return bascule(a);
    return a;
}

arbre essai_rotgauche(arbre a)
{
    if(rouge(a->droite) && rouge(a->droite->droite))
        return rotation_gauche(a);
    return a;
}

arbre essai_rotdroite(arbre a)
{
    if(rouge(a->gauche) && noir(a->droite))
        return rotation_droite(a);
    return a;
}

• essai_rotdroite fait pencher à droite un fils gauche rouge (si le fils droit est aussi rouge, c'est la bascule qui s'en chargera) ;
• essai_rotgauche traite deux rouges consécutifs à droite, qui deviennent les deux fils rouges d'un même nœud ;
• essai_bascule éclate alors ce nœud quaternaire.

L'évaluation paresseuse de && garantit qu'on n'accède à a->droite->droite que si a->droite est rouge, donc non vide.

Question 5

En déduire une fonction arbre insere(arbre a, int x) qui effectue l'insertion dans un arbre rouge et noir. On pourra définir une fonction auxiliaire arbre insere_aux(arbre a, int x) qui effectue l'insertion et qu'on appellera dans insere avant de faire le noircissement final de la racine.

Corrigé

arbre insere_aux(arbre a, int x)
{
    if (a == NULL)
        return cree_noeud(x);
    if (a->valeur > x)
        a->gauche = insere_aux(a->gauche, x);
    else
        a->droite = insere_aux(a->droite, x);
    return essai_bascule(essai_rotgauche(essai_rotdroite(a)));
}

arbre insere(arbre a, int x)
{
    arbre a2 = insere_aux(a, x);
    a2->rouge = false;
    return a2;
}

Les opérations de rééquilibrage sont effectuées en remontant, sur chaque nœud du chemin d'insertion : l'insertion est donc en \(O(h)\) où \(h\) est la hauteur de l'arbre, c'est-à-dire en \(O(\log n)\).

Pour tester, on peut écrire une fonction qui vérifie récursivement les propriétés rappelées au début (ABR, pas de fils gauche rouge, pas de rouge fils d'un rouge) et renvoie le nombre de nœuds noirs sur les chemins, en vérifiant qu'il est le même à gauche et à droite. Par exemple, après l'insertion de 1, 2, ..., 2000, l'arbre obtenu vérifie ces propriétés et a une hauteur de 15, contre 1999 pour un ABR sans rééquilibrage.