Voir la source de Arbre bicolore

Un '''arbre bicolore'''<ref>{{Ouvrage|langue=fr|prénom1=Vincent|nom1=Barra|titre=Informatique MP2I et MPI - CPGE 1re et 2e années - Nouveaux programmes|éditeur=Editions Ellipses|année=2021|date=|passage=105|isbn=978-2-340-05736-4|lire en ligne=https://books.google.com/books?id=2iFEEAAAQBAJ&newbks=0&printsec=frontcover&pg=PA105&dq=%22Arbre+bicolore%22+%22arbre+rouge-noir%22&hl=en|consulté le=2024-05-12}}</ref>, ou '''arbre rouge-noir<ref name="cl-intro-algo">{{Cormen2fr}}.</ref>'''  (en anglais ''{{lang|en|red–black tree}}'')<ref>{{Ouvrage|langue=en|prénom1=Thomas H.|nom1=Cormen|lien auteur1=Thomas H. Cormen|prénom2=Charles E.|nom2=Leiserson|lien auteur2=Charles E. Leiserson|prénom3=Ronald L.|nom3=Rivest|lien auteur3=Ronald Rivest|prénom4=Clifford|nom4=Stein|lien auteur4=Clifford Stein|titre=[[Introduction to Algorithms]]|éditeur=[[MIT Press]]|année=2009|numéro d'édition=3|passage=308-338|lire en ligne=|numéro chapitre=III 13|titre chapitre=Red-Black Trees|référence simplifiée=Référence:Introduction à l'algorithmique#MIT Press 2009}}</ref> ou '''arbre rouge et noir'''<ref>{{Lien web |titre=Arbres rouge et noir [rn] - Algorithmique - Introduction |url=https://ressources.unisciel.fr/algoprog/s46bst/emodules/rn00macours1/co/rn00macours1.html |site=[[Unisciel|ressources.unisciel.fr]] |consulté le=2024-05-12}}</ref> 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 ''{{Lang|en|symmetric binary B-trees}}'' (littéralement « [[Arbre B|arbres B]] binaires symétriques »)<ref name="Bayer72">{{article|auteur=Rudolf Bayer|titre=Symmetric binary B-Trees: Data structure and maintenance algorithms|journal=Acta Informatica|volume=1|numéro=4|année=1972|pages=290–306|url=https://link.springer.com/article/10.1007/BF00289509|doi=10.1007/BF00289509}}</ref>. 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<ref name=":0">{{Ouvrage|langue=en|prénom1=Thomas H.|nom1=Cormen|lien auteur1=Thomas H. Cormen|prénom2=Charles E.|nom2=Leiserson|lien auteur2=Charles E. Leiserson|prénom3=Ronald L.|nom3=Rivest|lien auteur3=Ronald L. Rivest|prénom4=Clifford|nom4=Stein|lien auteur4=Clifford Stein|titre=[[Introduction to Algorithms]]|lieu=Cambridge (Mass.)|éditeur=MIT Press|année=2001|numéro d'édition=second|pages totales=273–301|isbn=978-0-262-03293-3|isbn10=0-262-03293-7|bnf=38834736|titre chapitre=Red–Black Trees}}</ref>. 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 ==
{{Section vide ou incomplète}}
En 1972, Rudolf Bayer conçut une structure de données<ref name="Bayer72"/> 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 furent ensuite popularisés sous l'appellation d'[[arbre 2-3-4|arbres 2-3-4]].

Dans un article datant de 1978 intitulé ''A Dichromatic Framework for Balanced Trees''<ref>{{Article|prénom1=Leo J.|nom1=Guibas|prénom2=Robert|nom2=Sedgewick|titre=A dichromatic framework for balanced trees|périodique=(:unav)|date=1978-10|doi=10.1109/sfcs.1978.3|lire en ligne=http://ieeexplore.ieee.org/document/4567957/|consulté le=2019-03-25}}</ref>, [[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<ref>{{Lien web|titre=data structures - Where does the term "Red/Black Tree" come from?|url=https://softwareengineering.stackexchange.com/questions/116614/where-does-the-term-red-black-tree-come-from/116621|site=Software Engineering Stack Exchange|consulté le=2019-03-25}}</ref>.

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)''<ref name=":0" />

== 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îne de caractères|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 (programmation)|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 (informatique)|sentinelle]].

Comme tous les [[Arbre binaire de recherche|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 ===
[[Fichier:Red-black tree example.svg|360x360px|Exemple d'arbre bicolore. La hauteur noire de cet arbre est de 2.|alt=|vignette]]
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) :

# Un nœud est soit rouge soit noir ;
# La racine est noire ;
# Les enfants d'un nœud rouge sont noirs ;
# {{anchor|prop4}}Tous les chemins à partir d'un nœud jusqu'à ses feuilles, a le même nombre de nœuds noirs ;
# Toutes feuilles (NIL) sont noires<ref>{{Lien web |langue=en-US |titre=Introduction to Red-Black Tree |url=https://www.geeksforgeeks.org/introduction-to-red-black-tree/ |site=GeeksforGeeks |date=2014-02-04 |consulté le=2024-07-21}}</ref>.

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 [[arbre équilibré|é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 [[arbre binaire de recherche|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 [[#prop4|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 [[arbre AVL|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'[[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 [[Tableau associatif|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.

=== Opérations ===

La recherche sur un arbre bicolore s'effectue exactement comme dans les [[arbre binaire de recherche|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 (<math>O(\log(n))</math>) de modifications des couleurs (qui sont très rapides en pratique) et pas plus de trois [[rotation d'un arbre binaire de recherche|rotations]] (deux pour l'insertion). Ceci permet d'avoir une insertion et une suppression en <math>O(\log(n))</math> 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.<syntaxhighlight lang="c">
#define NOIR 0
#define ROUGE 1
#define FEUILLE NULL

struct noeud {
  struct noeud *gauche; //Pointeur vers fils gauche
  struct noeud *droit; //Pointeur vers fils droit 
  struct noeud *parent; //Pointeur vers père
  int couleur; // ROUGE ou NOIR
  int clé; // Peut être n'importe quel type, tant que les opérations de comparaison (<, = , > ) sont définies
};

</syntaxhighlight>On utilisera de plus les fonctions suivantes pour accéder à la « généalogie » d'un nœud donné (parent, grand-parent, etc.)<syntaxhighlight lang="c">
struct noeud* parent(struct noeud* n) {
  return n->parent;
}

struct noeud* grandparent(struct noeud* n) {
  struct noeud* p = parent(n);
  if (p == NULL)
    return NULL; // Un noeud sans parent n'a pas de grand-parent
  return parent(p);
}

struct noeud* frere(struct noeud* n) {
  struct noeud* p = parent(n);
  if (p == NULL)
    return NULL; // Un noeud sans parent n'a pas de frere
  if (n == p->gauche)
    return p->droit;
  else
    return p->gauche;
}

//Renvoie le frère du père
struct noeud* oncle(struct noeud* enfant) {
  struct noeud* p = parent(enfant);
  struct noeud* g = grandparent(enfant);
  if (g == NULL)
    return NULL; // Pas de grand parent, donc pas d'oncle
  return frere(p);
}
</syntaxhighlight>Enfin, on aura besoin des rotations d'arbres binaires :<syntaxhighlight lang="c">
void rotation_gauche(struct noeud* x) {
  struct noeud* y = x->droit;
  //le fils droit de x devient le fils gauche de y
  x->droit = y->gauche;
  if (y->gauche != FEUILLE)
    y->gauche->parent = x;
 
  y->parent = x->parent;
  //Si x est la racine, y devient la racine
  if (x->parent == NULL)
    x = y;

  //Sinon, on remplace x par y
  else if (x == x->parent->gauche)
    x->parent->gauche = y;
  else
    x->parent->droit = y;

  //On attache x à gauche de y
  y->gauche = x;
  x->parent = y;
}

void rotation_droite(struct noeud* x) {
  struct noeud* y = x->gauche;
  //le fils gauche de x devient le fils droit de y
  x->gauche = y->droit;
  if (y->droit != FEUILLE)
    y->droit->parent = x;
 
  y->parent = x->parent;
  //Si x est la racine, y devient la racine
  if (x->parent == NULL)
    x = y;

  //Sinon, on remplace x par y
  else if (x == x->parent->droit)
    x->parent->droit = y;
  else
    x->parent->gauche = y;

  //On attache x à droite de y
  y->droit = x;
  x->parent = y;
}
</syntaxhighlight>

==== 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. <syntaxhighlight lang="c">
struct noeud *insertion(struct noeud *racine, struct noeud *n) {
  // Insertion d'un nouveau nœud dans l'arbre
  insertion_recursif(racine, n);

  // Réparation de l'arbre au cas où les propriétés rouge-noir seraient violées
  insertion_repare_arbre(n);

  // Recherche de la nouvelle racine à renvoyer
  racine = n;
   
  while (parent(racine) != NULL)
    racine = parent(racine);
    
  return racine;
}

void insertion_recursif(struct noeud *racine, struct noeud *n) {
  // Descente récursive dans l'arbre jusqu'à atteindre une feuille
  if (racine != NULL && n->clé < racine->clé) {
    if (racine->gauche != FEUILLE) {
      insertion_recursif(racine->gauche, n);
      return;
    }
    else
      racine->gauche = n;
  } 
  else if (racine != NULL) {
    if (racine->droit != FEUILLE) {
      insertion_recursif(racine->droit, n);
      return;
	}
    else
      racine->droit = n;
  }

  // Insertion du nouveau noeud n
  n->parent = racine;
  n->gauche = FEUILLE; // NIL
  n->droit = FEUILLE; // NIL
  n->couleur = ROUGE;
}
</syntaxhighlight>

Une fois le nouveau nœud ajouté a l'arbre, il faut vérifier que les propriétés de l'arbre bicolore sont bien respectées et, dans le cas contraire, effectuer des opérations de changement de couleur et des rotations pour les rétablir. Le nœud inséré est initialement colorié en '''rouge'''. Il y a ensuite plusieurs cas possibles pour rétablir les propriétés de l'arbre, à partir du nœud inséré.

<syntaxhighlight lang="c">
void insertion_repare_arbre(struct noeud *n) {
   if (parent(n) == NULL)
      insertion_cas1(n);
   else if (parent(n)->couleur == NOIR)
      insertion_cas2(n);
   else if (oncle(n) != NULL && oncle(n)->couleur == ROUGE)
      insertion_cas3(n);
   else
      insertion_cas4(n);
 }
</syntaxhighlight>

# Le nœud inséré n'a pas de parent : il est en fait à la racine de l'arbre. La seule correction à apporter consiste à le colorier en '''noir''' pour respecter la propriété 2.<syntaxhighlight lang="c">
void insertion_cas1(struct noeud *n) {
   if (parent(n) == NULL)
      n->couleur = NOIR;
 }
</syntaxhighlight>
# Le parent du nœud inséré est '''noir''', alors l'arbre est valide : la propriété 3 est vérifiée, et la hauteur-noire de l'arbre est inchangée puisque le nouveau nœud est '''rouge'''. Il n'y a donc rien d'autre à faire.<syntaxhighlight lang="c">
void insertion_cas2(struct noeud *n) {
   return; /* Ne rien faire puisque l'arbre est bien un arbre rouge-noir */
 }
</syntaxhighlight>
# [[Fichier:Red-black tree insert case B1.svg|97x243px|Insérer cas 3|vignette]]Le parent du nœud inséré est '''rouge''', alors la propriété 3 est invalide. L'action à effectuer dépend de la couleur de l{{'}}''oncle'' du nœud inséré, c'est-à-dire le « frère » du parent du nœud inséré. En d'autres termes : en partant du nœud inséré (N), on considère son nœud parent (P), puis le nœud parent de P, ou grand-parent (G), et enfin l'oncle (U) qui est le fils de G qui n'est pas P. Si l'oncle est '''rouge''', alors le parent et l'oncle sont coloriés en '''noir''', et le grand-parent (qui était nécessairement noir) est colorié en '''rouge'''. Ce changement de couleur a pu toutefois créer une nouvelle violation des propriétés bicolores plus haut dans l'arbre. Il faut maintenant recommencer la même analyse de cas mais cette fois ''en partant du nœud grand-parent ainsi colorié en rouge''. <syntaxhighlight lang="c">
void insertion_cas3(struct noeud *n) {
   parent(n)->couleur = NOIR;
   oncle(n)->couleur = NOIR;
   
   struct noeud *g = grandparent(n);
   g->couleur = ROUGE;
   insertion_repare_arbre(g);
 }
</syntaxhighlight>
# [[Fichier:Red-black tree insert case C1.svg|97x320px|Insérer cas 4|vignette]]Dans le cas où l'oncle est '''noir''', il faut effectuer des rotations qui dépendent de la configuration du nœud inséré autour de son parent et de son grand-parent, afin de ramener l'équilibre dans l'arbre. <syntaxhighlight lang="c">
void insertion_cas4(struct noeud *n) {
   struct noeud *p = parent(n);
   struct noeud *g = grandparent(n);

   if (n == g->gauche->droit) {
      rotation_gauche(p);
      n = n->gauche;
   } else if (n == g->droit->gauche) {
      rotation_droit(p);
      n = n->droit; 
   }

   insertion_cas5(n);
 }
</syntaxhighlight>
# [[Fichier:Red-black tree insert case D1.svg|97x210px|Insérer cas 5|vignette]]Le parent vient prendre la place du grand-parent, et le grand-parent celle de l'oncle. Le parent devient '''noir''' et le grand-parent '''rouge''' et l'arbre respecte alors les propriétés bicolores. <syntaxhighlight lang="c">
void insertion_cas5(struct node *n) {
   struct noeud *p = parent(n);
   struct noeud *g = grandparent(n);

   if (n == p->gauche)
      rotation_droit(g);
   else
      rotation_gauche(g);
  
   p->couleur = NOIR;
   g->couleur = ROUGE;
 }

</syntaxhighlight>

Le seul cas où la correction ne se termine pas immédiatement est le cas 3, dans lequel on change le grand-parent de noir à rouge, ce qui oblige à effectuer une nouvelle vérification en partant du grand-parent. Cependant, il est aisé de vérifier que la fonction se termine toujours. Puisque le nœud à vérifier est toujours strictement plus haut que le précédent, on finira inévitablement par se retrouver dans l'un des cas non récursifs (dans le pire des cas, on remontera jusqu’à atteindre la racine de l'arbre, c'est-à-dire le cas 1). Il y aura donc au plus deux rotations, et un nombre de changements de couleurs inférieur à la moitié de la hauteur de l'arbre, c'est-à-dire en O(log ''n''). En pratique la probabilité de tomber plusieurs fois de suite sur le cas 3 est exponentiellement décroissante ; en moyenne le coût de la correction des propriétés est donc presque constant.

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

On notera qu'on peut toujours se mettre dans le cas où le nœud à supprimer a ''au plus'' un enfant qui ne soit pas une feuille. Dans le cas où le nœud à retirer aurait deux enfants qui ne sont pas des feuilles, on recherche soit le [[Extremum|plus grand élément]] du sous-arbre gauche (c'est-à-dire l'élément précédent immédiatement le nœud à supprimer dans l'ordre de l'arbre) soit le plus petit élément du sous-arbre droit (c'est-à-dire le successeur immédiat). La valeur du nœud à supprimer est remplacée par celle du prédécesseur ou du successeur, et c'est ce dernier nœud dont on vient de recopier la valeur qui est supprimé. On notera que la copie d'une valeur n'altère pas les propriétés bicolores de l'arbre.

Le nœud qui sera effectivement supprimé de l'arbre aura donc au plus un seul enfant qui ne soit pas une feuille. On note M le nœud à supprimer. M a donc soit un enfant non-feuille (noté C) soit aucun (dans ce cas, on choisit l'une des feuilles pour C). Après la suppression, la position qu'occupait M dans l'arbre sera occupée par C.

Dans le cas le plus simple, le nœud supprimé M est '''rouge''' : il suffit de le remplacer par son enfant C qui est nécessairement '''noir''' en vertu de la propriété 3. En retirant M, on ne change pas la hauteur-noire de l'arbre, donc les propriétés restent toutes respectées.

Un autre cas simple se produit si le nœud supprimé M est '''noir''' mais que son enfant C est '''rouge'''. En supprimant M, on diminue la hauteur-noire de l'arbre, ce qui violerait la propriété 5. De plus le parent P de M pourrait être rouge : or C va remplacer M comme fils de P, ce qui pourrait également violer la propriété 3. On restaure ces propriétés simplement en coloriant C en '''noir'''.

Le cas le plus compliqué se produit si le nœud supprimé M et son enfant C sont tous deux '''noirs'''.

== Notes et références ==
{{Références}}

{{Palette|Arbres informatiques|Structure de données}}
{{Portail|informatique théorique}}

[[Catégorie:Arbre (structure de données)]]