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.
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?
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 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]
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.
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) :
Un nœud est soit rouge soit noir ;
La racine est noire ;
Les enfants d'un nœud rouge sont noirs ;
Tous les chemins à partir d'un nœud jusqu'à ses feuilles, a le même nombre de nœuds noirs ;
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.
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.
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'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.
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 () 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 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.
#define NOIR 0#define ROUGE 1#define FEUILLE NULLstructnoeud{structnoeud*gauche;//Pointeur vers fils gauchestructnoeud*droit;//Pointeur vers fils droit structnoeud*parent;//Pointeur vers pèreintcouleur;// ROUGE ou NOIRintclé;// Peut être n'importe quel type, tant que les opérations de comparaison (<, = , > ) sont définies};
On utilisera de plus les fonctions suivantes pour accéder à la « généalogie » d'un nœud donné (parent, grand-parent, etc.)
structnoeud*parent(structnoeud*n){returnn->parent;}structnoeud*grandparent(structnoeud*n){structnoeud*p=parent(n);if(p==NULL)returnNULL;// Un noeud sans parent n'a pas de grand-parentreturnparent(p);}structnoeud*frere(structnoeud*n){structnoeud*p=parent(n);if(p==NULL)returnNULL;// Un noeud sans parent n'a pas de frereif(n==p->gauche)returnp->droit;elsereturnp->gauche;}//Renvoie le frère du pèrestructnoeud*oncle(structnoeud*enfant){structnoeud*p=parent(enfant);structnoeud*g=grandparent(enfant);if(g==NULL)returnNULL;// Pas de grand parent, donc pas d'onclereturnfrere(p);}
Enfin, on aura besoin des rotations d'arbres binaires :
voidrotation_gauche(structnoeud*x){structnoeud*y=x->droit;//le fils droit de x devient le fils gauche de yx->droit=y->gauche;if(y->gauche!=FEUILLE)y->gauche->parent=x;y->parent=x->parent;//Si x est la racine, y devient la racineif(x->parent==NULL)x=y;//Sinon, on remplace x par yelseif(x==x->parent->gauche)x->parent->gauche=y;elsex->parent->droit=y;//On attache x à gauche de yy->gauche=x;x->parent=y;}voidrotation_droite(structnoeud*x){structnoeud*y=x->gauche;//le fils gauche de x devient le fils droit de yx->gauche=y->droit;if(y->droit!=FEUILLE)y->droit->parent=x;y->parent=x->parent;//Si x est la racine, y devient la racineif(x->parent==NULL)x=y;//Sinon, on remplace x par yelseif(x==x->parent->droit)x->parent->droit=y;elsex->parent->gauche=y;//On attache x à droite de yy->droit=x;x->parent=y;}
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.
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.
structnoeud*insertion(structnoeud*racine,structnoeud*n){// Insertion d'un nouveau nœud dans l'arbreinsertion_recursif(racine,n);// Réparation de l'arbre au cas où les propriétés rouge-noir seraient violéesinsertion_repare_arbre(n);// Recherche de la nouvelle racine à renvoyerracine=n;while(parent(racine)!=NULL)racine=parent(racine);returnracine;}voidinsertion_recursif(structnoeud*racine,structnoeud*n){// Descente récursive dans l'arbre jusqu'à atteindre une feuilleif(racine!=NULL&&n->clé<racine->clé){if(racine->gauche!=FEUILLE){insertion_recursif(racine->gauche,n);return;}elseracine->gauche=n;}elseif(racine!=NULL){if(racine->droit!=FEUILLE){insertion_recursif(racine->droit,n);return;}elseracine->droit=n;}// Insertion du nouveau noeud nn->parent=racine;n->gauche=FEUILLE;// NILn->droit=FEUILLE;// NILn->couleur=ROUGE;}
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é.
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.
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.
voidinsertion_cas2(structnoeud*n){return;/* Ne rien faire puisque l'arbre est bien un arbre rouge-noir */}
Insérer cas 3Le 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.
Insérer cas 4Dans 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.
Insérer cas 5Le 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.
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.
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 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.
↑Vincent Barra, Informatique MP2I et MPI - CPGE 1re et 2e années - Nouveaux programmes, Editions Ellipses, (ISBN978-2-340-05736-4, lire en ligne), p. 105
↑ a et bRudolf Bayer, « Symmetric binary B-Trees: Data structure and maintenance algorithms », Acta Informatica, vol. 1, no 4, , p. 290–306 (DOI10.1007/BF00289509, lire en ligne)
