Arbre Rouge Noir

PrésentationInventé en 1972 par Rudolf Bayer;Une arbre rouge noir (arbre bicolore) est un

type d’implantation d’arbre binaire couramment utilisé;

Les arbres rouges noirs offrent certains avantages qui fait en sorte qu’ils sont préférés aux arbres AVL;

Cependant, l’efficacité des arbres rouges noirs ce traduit par une plus grande complexité d’implémentation;

Les arbres AVL sont plus utilisés au niveau académique.

Propriétés Un arbre rouge et noir doit respecter les

cinq propriétés suivantes:1. Un nœud est soit rouge ou noir;2. Une feuille doit être noir ou « Nil »;3. La racine doit être noire * ;4. Un parent rouge doit avoir deux fils noirs;5. Chaque chemin d’une feuille à la racine doit

toujours comporter le même nombre de nœuds noirs.

* Cette règle peut être facultative car elle n’a pas d’impact sur l’efficacité de l’arbre.

Recherche dans l’arbreLa recherche s’effectue exactement comme

dans tout les arbres binaires et avec la même efficacité algorithmique ( O(log N) );

La recherche est une opération préliminaire à l’insertion et à la suppression;

Insertion et suppressionLors des insertions et des suppressions des

nœuds de l’arbre, les 5 propriétés des arbres rouges noirs doivent être respectées.

La conséquence est qu’il y a de nombreux cas possibles.

Cela contribue à la complexité de l’arbre rouge noir (comparativement à l’arbre AVL)

InsertionUn nouveau nœud est toujours ROUGE.Il n’y a aucun problème à moins que le nœud

parent soit aussi rouge.Si le parent est rouge, on est dans un cas

spécifique, il y faut appliquer le bon algorithme pour rétablir les propriétés de l’arbre rouge noir.

Insertion – NotationVoici la notation qui est utilisé pour identifier

les nœuds de l’arbre« P » : Le nœud parent« PP » : Le nœud grand-parent« O » : Le nœud oncle« X » : Nouveau nœud et nœud courant

Insertion – Cas 0Si « P » est la racine de l’arbre.C’est le seul cas où la hauteur noire de

l’arbre augmente.

Insertion – Cas 1Si « O » est rouge« P » et « O » deviennent noirs, « PP »

devient rouge**Ce cas n’est pas toujours final

Insertion – Cas 2« O » est noirCe dernier cas à quatre variantes, tout

dépendant de la position de « X » et « P » par rapport à leur parent.

Dans certaines explications, on prend en considération la symétrie des opérations, mais cela peut être une source d’erreur si la notion est mal comprise.

Insertion – Cas 2a« X » et « P » sont des fils de gauche

Insertion – Cas 2b« X » et « P » sont des fils de droite

Insertion – Cas 2c« X » est un fils droit, et « P » est un fils

gauche

Insertion – Cas 2d« X » est un fils gauche, et « P » est un fils

droit

SuppressionSi le nœud supprimé est rouge, toutes les

propriétés restes intactes.Les cas spécifiques concernent les cas où le

nœud supprimé est noir

SuppressionLe nœud à supprimer n’est pas tout le temps

le nœud qui contient la valeur à supprimer de l’arbre.

Si le nœud a zéro ou un fils, on le supprime, et c’est potentiellement son fils qui prend sa place.

Si le nœud a 2 fils (on ne considère pas les NIL), on échange sa valeur avec le nœud le plus à gauche de son sous-arbre droit, et c’est ce nœud le plus à gauche que l’on supprime

SuppressionLe nœud supprimé, ou le nœud qui remplace

celui qui a été supprimé, doit avoir une deuxième couleur noire pour faire respecter la 5e propriété de l’arbre rouge noir.

Si le nœud auquel on ajoute une couleur noire est rouge, il devient noir et le cas prend fin.

Si le nœud est déjà noir, il devient doublement noir, et il faut appliquer les cas spécifiques de suppression pour enlever la double couleur noire.

Suppression – NotationVoici la notation qui sera utilisée pour les cas

de suppression

« X » est le nœud qui à la double couleur (courant)

« P » est le nœud parent« F » est le nœud frère de « X »« G » est le nœud fils gauche de « F »« D » est le nœud fils droit de « F »

Suppression Cas 0« X » est la racine de l’arbreOn annule simplement la double couleur

noireC’est le seul cas où la hauteur noire de

l’arbre diminue

Suppression – Cas 1« F » est noirCe cas à cinq variantes, dont deux paires de

cas qui sont symétriques. Les cas symétrique sont présenté individuellement par soucis de clarté.

Suppression – Cas 1a« G » et « D » sont noirsLa double couleur est propagée vers le nœud

« P »Ce cas n’est pas final

Suppression – Cas 1b« D » est rouge, et « F » est un fils droit

Suppression – Cas 1c« G » est rouge, et « F » est un fils gauche

Suppression – Cas 1d« G » est rouge, « D » est noir, « F » fils de

droite

Suppression – Cas 1e« G » est noir, « D » est rouge, « F » fils de

gauche

Suppression – Cas 2« F » est rougeEncore une fois les 2 variantes symétriques

sont présentées individuellement.

Suppression – Cas 2a« F » est un fils de gauche

Suppression – Cas 2b« F » est un fils de droit

Analyse et comparaison AVL