Arbre bicolore

Un arbre bicolore^[1], ou arbre rouge-noir^[2] (en anglais red–black tree)^[3] ou arbre rouge et noir^[4] est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »)^[5]. Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les nœuds et leurs couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris dans le pire des cas. Durant une insertion ou une suppression, les nœuds sont parfois réarrangés ou changent leur couleur afin que ces propriétés soient conservées.

Grâce à ces réarrangements ou coloriages des nœuds, la complexité en temps des opérations d'insertion, de recherche et de suppression est logarithmique en rapport au nombre d'éléments de la structure^[6]. De plus, par rapport à un arbre binaire basique, cette structure est économe en mémoire puisque chaque nœud ne requiert qu'un bit supplémentaire pour stocker la couleur.

Histoire

En 1972, Rudolf Bayer conçut une structure de données^[5] qui était un cas particulier d'arbre B d'ordre 4 dans lequel chaque chemin entre la racine et les feuilles de l'arbre avait le même nombre de nœuds, ce qui en faisait des arbres parfaitement équilibrés (sans toutefois être des arbres binaires de recherche). Bayer les nomma « arbres B binaires symétriques », et ils furent ensuite popularisés sous l'appellation d'arbres 2-3-4.

Dans un article datant de 1978 intitulé A Dichromatic Framework for Balanced Trees^[7], Leonidas John Guibas et Robert Sedgewick construisirent les arbres rouge-noir à partir des arbres-B binaires symétriques. Les couleurs (rouge et noir) auraient été choisies parce qu'elles ressortaient mieux sur l'imprimante laser du Xerox PARC, ou simplement parce qu'ils n'avaient à disposition que ces couleurs de stylos^[8].

La description de référence des opérations sur les arbres bicolores (avec seulement 6 cas déséquilibrés au lieu des 8 originaux) est donnée dans le chapitre qui leur est consacré dans l'ouvrage Introduction à l'algorithmique (Cormen et al. 2001)^[6]

Présentation

Un arbre bicolore est un cas particulier d'arbre binaire, une structure de donnée couramment utilisée en informatique pour organiser des données pouvant être comparées, par exemple des nombres ou des chaînes de caractères.

Les feuilles de l'arbre, c'est-à-dire les nœuds terminaux, ne contiennent aucune donnée. Elles peuvent être simplement représentées sans coût mémoire par des éléments nuls (pointeur nul en C, valeur NIL, etc.) dans le nœud parent (indiquant que le nœud enfant est une feuille). Il peut être toutefois utile pour simplifier la mise en œuvre de certains algorithmes que les feuilles soient explicitement représentées soit en les instanciant séparément, soit en utilisant une sentinelle.

Comme tous les arbres binaires de recherche, les arbres bicolores peuvent être parcourus très efficacement en ordre infixe (ou ordre gauche - racine - droite), ce qui permet de lister les éléments dans l'ordre. La recherche d'un élément se fait en temps logarithmique O(log n), n étant le nombre d'éléments de l'arbre, y compris dans le pire des cas.

Propriétés

Exemple d'arbre bicolore. La hauteur noire de cet arbre est de 2.

Un arbre bicolore est un arbre binaire de recherche dans lequel chaque nœud a un attribut supplémentaire d'une valeur d'un bit, et qui permet donc de distinguer deux types d'éléments. Cet attribut est la couleur de chaque nœud, par exemple dans le cas d'un arbre rouge-noir, soit « rouge » soit « noire » (on peut tout aussi bien dire « gauche » / « droite », « coloré » ou « noir » / « non coloré » ou « blanc »). En plus des restrictions imposées aux arbres binaires de recherche, les règles suivantes sont utilisées (dans la suite du paragraphe on prend l'exemple de l'arbre rouge-noir) :

1. Un nœud est soit rouge soit noir ;
2. Les enfants d'un nœud rouge sont noirs ;
3. Tous les chemins à partir d'un nœud jusqu'à ses feuilles, a le même nombre de nœuds noirs ;
4. Toutes feuilles (NIL) sont noires^[9].

Ces contraintes impliquent une propriété importante des arbres bicolores : le chemin le plus long possible d'une racine à une feuille (sa hauteur) ne peut être que deux fois plus long que le plus petit possible : dans le cas le plus déséquilibré, le plus court des chemins ne comporte que des nœuds noirs, et le plus long alterne les nœuds rouges et noirs. Un arbre vérifiant ces propriétés est ainsi presque équilibré. Comme les opérations d'insertion, de recherche et de suppression requièrent dans le pire des cas un temps proportionnel à la hauteur de l'arbre, les arbres bicolores restent efficaces, contrairement aux arbres binaires de recherche ordinaires.

Pour comprendre comment ces contraintes garantissent la propriété ci-dessus, il suffit de s'apercevoir qu'aucun chemin ne peut avoir deux nœuds rouges consécutifs à cause de la propriété 3. Le plus petit chemin théorique de la racine à une feuille ne contient alors que des nœuds noirs tandis que le plus grand alterne entre les nœuds rouges et noirs. Et comme d'après la propriété 5 chacun de ces chemins contient le même nombre de nœuds noirs, le plus grand chemin ne peut être deux fois plus grand que le plus petit.

La propriété 2 n'est pas nécessaire. Les seuls cas où la racine pourrait devenir rouge étant les deux cas où sa couleur n'a pas d'importance : soit la racine est le seul nœud, soit elle possède deux fils noirs. Cette propriété est ajoutée uniquement pour visualiser plus rapidement l'isomorphisme avec les arbres 2-3-4 : chaque nœud noir et ses éventuels fils rouges représente un nœud d'arbre 2-3-4.

Terminologie

La profondeur noire d'un nœud est définie comme le nombre de nœuds noirs dans le chemin reliant la racine à ce nœud, c'est-à-dire son nombre de prédécesseurs noirs. La hauteur noire d'un arbre rouge-noir est le nombre de nœuds noirs dans le chemin de la racine à n'importe quelle feuille, ce nombre étant constant par la propriété 4. Cette dernière pourrait aussi être définie comme la profondeur noire de n'importe laquelle des feuilles. La hauteur noire d'un nœud correspond à la hauteur noire du sous-arbre dont il est racine.

Utilisation et avantages

Les arbres bicolores, ainsi que les arbres AVL, offrent la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables. Ceci leur permet non seulement d'être alors utilisables dans des applications en temps réel, mais aussi de servir comme fondement d'autres structures de données à temps d'exécution garanti dans les cas défavorables, par exemple en géométrie algorithmique. L'ancien ordonnanceur du noyau Linux, le Completely Fair Scheduler utilise également un arbre rouge-noir.

Les arbres rouge-noir sont également très utile en programmation fonctionnelle : c'est l'exemple le plus couramment utilisé de structure de données persistante qui peut être utilisée pour construire des tableaux associatifs capables de garder en mémoires les versions précédentes après un changement. Les versions persistantes des arbres rouge-noir requièrent O(log n) en mémoire supplémentaire pour chaque insertion ou suppressions.

Implémentations

La recherche sur un arbre bicolore s'effectue exactement comme dans les arbres binaires de recherche. Cependant, après une insertion ou une suppression, les propriétés de l'arbre bicolore peuvent être violées. La restauration de ces propriétés requiert un petit nombre (${\displaystyle O(\log(n))}$) de modifications des couleurs (qui sont très rapides en pratique) et pas plus de trois rotations (deux pour l'insertion). Ceci permet d'avoir une insertion et une suppression en ${\displaystyle O(\log(n))}$ mais rend l'implémentation plus complexe à cause du grand nombre de cas particuliers à traiter.

Dans cette partie, on illustrera les opérations à l'aide d'une implémentation en C reposant sur la définition suivante de la structure d'arbre.

enum couleur {ROUGE, NOIR};
enum dir {GAUCHE, DROITE};
#define FEUILLE NULL

struct noeud { 
  struct noeud *parent; //Pointeur vers père
  union { // On peut soit réferer à n.gauche ou n.fils[GAUCHE]
    struct {
      struct noeud *gauche;
      struct noeud *droite;
    };
    struct noeud *fils[2];
  };
  enum couleur couleur; // ROUGE ou NOIR
  int cle; // Peut être n'importe quel type, tant que les opérations de comparaison (<, = , > ) sont définies
};

Enfin, on aura besoin des rotations d'arbres binaires:

Rotation a gauche
et à droite animées.

void rotation(struct noeud *n, dir_t dir) {
    struct noeud *p = n->parent;
    struct noeud *racine = n->fils[1 - dir]; // La nouvelle racine
    struct noeud *fils = racine->fils[dir];

    n->child[1 - dir] = child;
    if (child) child->parent = n;

    racine->parent = p;
    if (p)
        p->child[DIR(n)] = racine;

    n->parent = root;
    racine->child[dir] = n;
}

Note sur les différentes notations utilisées

Notations utilisées

Dans toutes la suite on notera N le nœud courant, P son parent, G son grand-parent, S son frère, C son neveu dans la même direction, D son neveu dans la direction opposée et U son oncle. Ce qui donne dans le cas où la direction de P et N est la gauche.

Recherche d'un élément

La recherche d'un élément se déroule de la même façon que pour un arbre binaire de recherche : en partant de la racine, on compare la valeur recherchée à celle du nœud courant de l'arbre. Si ces valeurs sont égales, la recherche est terminée et on renvoie le nœud courant. Sinon, on choisit de descendre vers le nœud enfant gauche ou droit selon que la valeur recherchée est inférieure ou supérieure. Si une feuille est atteinte, la valeur recherchée ne se trouve pas dans l'arbre.

La couleur des nœuds de l'arbre n'intervient pas directement dans la recherche. Toutefois à la différence d'un arbre binaire de recherche normal, les arbres rouge-noir garantissent par construction un temps d’exécution de la recherche en O(log n) y compris dans le pire des cas. En effet, un arbre binaire de recherche peut devenir déséquilibré dans des cas défavorables (par exemple si les éléments sont insérés dans l'ordre croissant, l'arbre binaire de recherche dégénère en une liste chaînée). La complexité de l'opération dans le pire des cas est donc O(n) pour un arbre binaire potentiellement non équilibré. Au contraire, pour l'arbre rouge-noir, les propriétés bicolores vues ci-dessus garantissent que l'on atteindra un nœud en au plus 2 log n comparaisons, donc en O(log n) opérations.

Insertion

L'insertion commence de la même manière que sur un arbre binaire classique : en partant de la racine, on compare la valeur insérée à celle du nœud courant de l'arbre, et on choisit de descendre vers le nœud enfant gauche ou droit selon que la valeur insérée est inférieure ou supérieure. Le nouveau nœud est inséré lorsque l'on ne peut plus descendre, c'est-à-dire quand le nœud courant est une feuille de l'arbre. Cette feuille est remplacée par le nouveau nœud.

Une fois le nouveau nœud ajouté a l'arbre, on le colorie en rouge de manière à ne pas violer la propriété 4. Cependant on a potentiellement violé les autres propriétés, par exemple si le parent de est également rouge. Pour pallier ce problème on remonter l'arbre à partir de N. Ce qui conduit à une boucle d'équilibrage qui a les invariants suivants:

• N est le nœud courant, initialement celui inséré
• N est rouge
• La propriété 3 est satisfaite pour chaque pair enfant-parent, avec une exception possible pour la paire N-P
• Les autres propriétés sont satisfaites dans tout l'arbre

Note sur la table d'insertion

Avant				Cas	Après				Prochaine étape
P	G	U	x		P	G	U	x
				I1
				I2	?				?
—				I3
	—			I4
			i	I5				e	I6
			e	I6
Insertion Cette table montre dans sa colonne avant, que l'ensemble des cas possibles[10] est couvert.

• L'ensemble des diagrammes considère que P est l'enfant gauche de G, alors qu'il pourrait très bien être l'enfant droite. Ces 2 possibilités sont gérés par la variable dir dans les codes d'exemples.
• Dans la table "—" indique que le nœud est nul.

Une config extérieur

Une config intérieur

Exemple de configuration

• Les colonnes x indique le changement de direction de N par rapport a P: i (pour intérieur) indique que N et P sont de directions opposés, alors que e (pour extérieur) indique qu'ils ont la même direction
• Les colonnes avant décrive les différents cas possibles avant itération. Une absence de valeur indique celle-ci n'influe pas dans le cas a appliquer. Par exemple dans le I1, les couleurs de G et U peuvent-être aussi bien rouge que noir.
• Si le cas a modifié l'arbre les différents changements sont illustrés dans les colonnes après. (Attention certains cas modifie le nœud courant et donc possiblement tous les autres).
• Un signe dans la colonne Prochaine étape indique que l'équilibrage se finit avec cette étape

Cas 1 d'insertion

P est noir, donc la propriétés 3 est vrai. L'arbre total est donc valide on peut s'arrêter.

Cas 2 d'insertion

Première itération

Autre itération

Cas 2

Si P et U sont rouge, G est nécessairement noir et alors on peut le colorier en rouge et colorier P et U en noir ce qui permet de conserver la propriété 4. la paire N-P respecte alors la propriété 3, mais G peut la violer. Après le changement de notation G devient N l'invariant de boucle et de nouveau respecté et on continuer.

Cas 3 d'insertion

N est la racine de l'arbre est alors les invariants de boucle garantissent que l'arbre est valide.

Cas 4 d'insertion

P est rouge mais également la racine de l'arbre. On peut donc colorier P en noir pour satisfaire la propriété 3

Cas 5 d'insertion

première iteration

autre iteration

Cas 5

P est rouge mais U est noir, le but est alors de se rapporter dans une situation similaire au cas 2. Pour cela on aimerait faire en sorte que P devienne la racine du sous-arbre G. On peut le faire en utilisant les opérations de rotations, mais pour conserver la relation de parenté entre P et N il faut que l'on se trouve dans la configuration extérieur. On fait donc une première rotation entre entre P et N. Comme les deux sont rouge, 4 est conservé. Et après une changement de notation P devient N on se rapporte au cas 6.

Cas 6 d'insertion

première iteration

autre iteration

Cas 6

On est désormais dans une configuration extérieur et on peut donc effectuer une rotation entre P et G. Puis on colorie P en noir et G en rouge ce qui permet de satisfaire à 3. Et 4 est conservé car tous les chemins qui passaient par G noir passent désormais par P noir.

Fonction d'équilibrage

En cumulant tous ces cas on obtient une fonction d'équilibrage après insertion

void equilibrage_insertion(struct noeud *n, struct noeud *parent) {
    // Cas 3
    if (!parent) {
        n->couleur = NOIR;
        return;
    }

    do {
        // Cas 1
        if (parent->couleur == NOIR) return;

        struct noeud *gp = parent->parent;

        // Gas 4
        if (!gp) {
            parent->couleur = NOIR;
            return;
        }

        dir_t dir = DIR(parent);
        struct noeud *oncle = gp->fils[1 - dir];
        if (!oncle || oncle->couleur == NOIR) {
            if (n == parent->fils[1 - dir]) {
                // Cas 5
                rotate(parent, dir);
                n = parent;
                parent = gp->fils[dir];
            }

            // Cas 6
            rotate(gp, 1 - dir);
            gp->couleur = RED;
            parent->couleur = NOIR;
            return;
        }

        // Cas 2
        parent->couleur = NOIR;
        oncle->couleur = NOIR;
        gp->couleur = RED;
        n = gp;

    } while ((parent = n->parent));

    return;
}

Suppression

La suppression commence par une recherche du nœud à supprimer, comme dans un arbre binaire classique.

Cas de base

On peut alors se trouver dans un des 5 cas de base, 4 d'entre eux sont rapides à traiter et le dernier est la suppression d'une feuille noire. Ces cas sont :

• N a 2 enfants (non nul), on échange alors la valeur de N avec celle du nœud N' le plus à droite du sous arbre N->gauche. Cet échange, suivie de la suppression N' permet la préservation des propriétés d'un arbre de recherche. Et alors en remplaçant N par N' on se trouve dans l'un des 4 cas restants. Car N' étant le nœud le plus à droite d'un sous arbre binaire, il ne peut pas avoir d'enfant non nul droit.
• Si N a un unique enfant, la propriété 4 assure que cet enfant est de couleur rouge. On peut alors échanger les valeurs de N et de son fils et supprimer le fils, ce qui conclut la suppression.
• Si N n'a pas d'enfant et est la racine de l'arbre, on supprime N, l'arbre devient l'arbre valide qui est valide.
• Si N n'a pas d'enfant et qu'il est rouge, on peut le supprimer sans violer de contrainte.
• Si N n'a pas d'enfant et qu'il est noir, sa suppression viole la propriété 4, la partie suivante traite de comment la rétablir.

Suppression d'une feuille noire

De la même manière que pour l'insertion, on va remonter l'arbre pour corriger le déséquilibre créé par la suppression. On a donc une boucle avec les invariants suivants :

• N est noir
• Le nombre de nœuds noirs sur les chemins passant par N est diminué de 1 comparé à celui avant la suppression. Il est inchangé sur tous les autres. On a donc une violation de {{#prop4|4}} s'il existe de tel autre chemin.
• Toutes les autres propriétés des arbres bicolores sont satisfaites.

Note sur la table de suppression

Avant				Cas	After				Prochaine étape
P	S	C	D		P	S	C	D
—				D1
				D2	?				?
				D3			?		?
				D4
				D5					D6
				D6
Suppression Ce tableau montre que tous les cas possible de couleur sont bien traités

• Dans les diagrammes, N est considéré comme étant le fils gauche de P même si ce n'est pas garanti que ce soit le cas. Cette possibilité est gérée par la variable dir dans la fonction d'exemple.
• Lors de la première itération, N est un nœud qui remplace le nœud à supprimer. Sa seule importance est son existence par rapport à P, il est représenté par dans la partie de gauche des diagrammes. Pour les autres itération N est devenu un nœud non nul et est bien représenté.
• Les colonnes Avant décrivent les différents cas possibles. Une absence de valeur indique que celle-ci n'influe pas dans le choix du cas à appliquer.
• Un signe dans la colonne Prochaine étape indique que ce cas finit l'équilibrage de l'arbre.

Suppression cas 1

N est la racine, tous les chemins passent par N, l'arbre est valide, on s'arrête.

Suppression cas 2

première iteration

autre iteration

Suppression cas 2

P, S et les fils de S sont tous noirs, en coloriant S en rouge, on décrémente le nombre de nœuds noirs sur les chemins passant par S, de sorte qu'il y en ai autant que sur les chemins passant par N. Après le changement P devient N, les invariants sont de nouveau vérifiés, on continue d'itérer.

Suppression cas 3

première iteration

autre iteration

Suppression cas 3

S est rouge, donc nécessairement P, C et D sont noirs. Une rotation entre S et P transforme S en le grand-parent de N. Un échange des couleurs de S et P permet de conserver le nombre de nœuds noirs sur les chemins passant par D. Cependant, il y a toujours un déséquilibre en N, mais avec les notations adaptées au changement de structure de l'arbre. On a désormais P rouge et on est dans l'un des cas qui suivent.

Suppression cas 4

première iteration

autre iteration

Suppression cas 4

S et ses fils sont noirs mais P est rouge. On peut échange les couleurs de S et P sans violer 3. Mais on a incrémenté le nombre de nœuds noirs passant par N, ce qui termine l'équilibrage

Suppression cas 5

première iteration

autre iteration

Delete case D5

S et D sont noirs, C est rouge. Une rotation entre S et C transforme C en le nouveau frère de N. On échange les couleurs de S et C pour garder constant le nombre de nœuds noirs des chemins passant par C. Après mise à jour des notations, on se trouve dans le cas 6.

Suppression cas 6

première iteration

autre iteration

Delete case D6

S est noir et D est rouge. Après une rotation entre S et P, S est devenu le parent de P. On inverse les couleurs de S et P et on colorie D en noir. Le sous-arbre que l'on modifie à toujours la même couleur de racine, ce qui garantit que 3 est préservé. Les chemins passant par D et le sous arbre 3 (i.e ceux qui ne passent pas par N) ont conservé le nombre de nœuds noirs qu'ils traversent. Et on a ajouté un nœud noir pour les chemins passant par N: soit P est devenu noir, soit P était noir et on a ajouté S en tant qu'ancêtre noir. La propriété 4 est donc maintenant respecté dans tous l'arbre, l'équilibrage est fini.

Fonction d'équilibrage

On peut alors écrire une fonction d'équilibrage pour la suppression d'un nœud noir:

void equilibrage_suppresion(struct noeud *n) {
    struct noeud *p;
    struct noeud *s;
    struct noeud *c;
    struct noeud *d;

    do {
        dir dir = DIR(n);
        p = n->parent;
        s = p->fils[1 - dir];
        c = s->fils[dir];
        d = s->fils[1 - dir];

        // Cas 3
        if (s->couleur == ROUGE) {
            rotate(p, dir);
            p->couleur = ROUGE;
            s->couleur = NOIR;
            s = c;
            c = s->fils[dir];
            d = s->fils[1 - dir];
        }

        if (!d || d->couleur == NOIR) {
            if (!c || c->couleur == NOIR) {
                s->couleur = ROUGE;
                if (p->couleur == NOIR) {
                    // Cas 2
                    continue;
                } else {
                    // Cas 4
                    p->couleur = NOIR;
                    return;
                }
            } else {
                // Cas 5
                rotate(s, 1 - dir);
                c->couleur = NOIR;
                s->couleur = ROUGE;
                d = s;
                s = c;
            }
        }

        // Cas 6
        rotate(p, dir);
        s->couleur = p->couleur;
        p->couleur = NOIR;
        d->couleur = NOIR;
        return;
    } while ((n = n->parent) && n->parent);

    // Cas 1
    return;
}