Arbre bicolore

Un arbre bicolore^{[réf. nécessaire]}, ou arbre rouge-noir^[1] ou arbre rouge et noir^{[réf. nécessaire]} 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 »)^[2]. 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.

Le principal intérêt des arbres bicolores réside dans le fait que malgré les potentiels réarrangements ou coloriages des nœuds, la complexité (en le nombre d'éléments) des opérations d'insertion, de recherche et de suppression est logarithmique^[3]. De plus, cette structure est économe en mémoire puisqu'elle ne requiert qu'un bit supplémentaire d'information par élément par rapport à un arbre binaire classique.

Histoire[modifier | modifier le code]

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^[2] 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^[4], 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^[5].

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)^[3]

Définitions[modifier | modifier le code]

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[modifier | modifier le code]

Un arbre bicolore est un arbre binaire de recherche dans lequel chaque nœud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire. En plus des restrictions imposées aux arbres binaires de recherche, les règles suivantes sont utilisées :

Un nœud est soit rouge soit noir ;
La racine est noire ;
Les enfants d'un nœud rouge sont noirs;
Tous les nœuds ont 2 enfants. Ce sont d'autres nœuds ou des feuilles NIL, qui ne possèdent pas de valeur et qui sont les seuls nœuds sans enfants. Leur couleur est toujours noire et rentre donc en compte lors du calcul de la hauteur noire.
Le chemin de la racine à n'importe quelle feuille (NIL) contient le même nombre de nœuds noirs. On peut appeler ce nombre de nœuds noirs la hauteur noire.

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.

Utilisation et avantages[modifier | modifier le code]

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.

Opérations[modifier | modifier le code]

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 ( $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 $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.

#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
};

On utilisera de plus les fonctions suivantes pour accéder à la « généalogie » d'un nœud donné (parent, grand-parent, etc.)

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);
}

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

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;
}

Recherche d'un élément[modifier | modifier le code]

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[modifier | modifier le code]

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.

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;
}

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é.

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);
 }

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.
```
void insertion_cas1(struct noeud *n) {
   if (parent(n) == NULL)
      n->couleur = NOIR;
 }
```
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.
```
void insertion_cas2(struct noeud *n) {
   return; /* Ne rien faire puisque l'arbre est bien un arbre rouge-noir */
 }
```
Insérer cas 3
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.
```
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);
 }
```

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.

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);
 }

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.

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;
 }

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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition].
↑ ^{a et b} Rudolf Bayer, « Symmetric binary B-Trees: Data structure and maintenance algorithms », Acta Informatica, vol. 1, n^o 4,‎ 1972, p. 290–306 (DOI 10.1007/BF00289509, lire en ligne)
↑ ^{a et b} (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press, 2001, second éd., 273–301 p. (ISBN 978-0-262-03293-3, BNF 38834736), « Red–Black Trees »
↑ Leo J. Guibas et Robert Sedgewick, « A dichromatic framework for balanced trees », (:unav),‎ octobre 1978 (DOI 10.1109/sfcs.1978.3, lire en ligne, consulté le 25 mars 2019)
↑ « data structures - Where does the term "Red/Black Tree" come from? », sur Software Engineering Stack Exchange (consulté le 25 mars 2019)

Portail de l'informatique théorique

[cl-intro-algo-1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition].

[Bayer72-2] {a et b} Rudolf Bayer, « Symmetric binary B-Trees: Data structure and maintenance algorithms », Acta Informatica, vol. 1, n^o 4,‎ 1972, p. 290–306 (DOI 10.1007/BF00289509, lire en ligne)

[:0-3] {a et b} (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.), MIT Press, 2001, second éd., 273–301 p. (ISBN 978-0-262-03293-3, BNF 38834736), « Red–Black Trees »

[4] Leo J. Guibas et Robert Sedgewick, « A dichromatic framework for balanced trees », (:unav),‎ octobre 1978 (DOI 10.1109/sfcs.1978.3, lire en ligne, consulté le 25 mars 2019)

[5] « data structures - Where does the term "Red/Black Tree" come from? », sur Software Engineering Stack Exchange (consulté le 25 mars 2019)

[1]

[2]

[3]

[4]

[5]

v · m Arbre enraciné
Arbre binaire	Arbre binaire de recherche Arbre de fouille Arbre cartésien MVP Tree (en) Top tree (en) T-tree (en)
Arbre équilibré	AA tree (en) Arbre AVL LLRB tree (en) Arbre bicolore Arbre bouc-émissaire Arbre splay Treap
Arbre B	B*-tree (en) Bx-tree (en) UB-tree (en) 2-3 tree (en) Arbre 2-3-4 (a,b)-tree (en) Dancing tree Htree (en)
Trie	Arbre des suffixes Arbre radix Arbre ternaire de recherche X-fast trie (en) Y-fast trie (en)
Partition binaire de l'espace trees	Quadtree Octree Arbre kd (relaxé) Implicit k-d tree (en) Vp-tree
Arbres non binaires	Arbre exponentiel Fusion tree (en) arbre d'intervalles arbre PQ arbre de portée (range tree) arbre SPQR arbre de Van Emde Boas
Arbre de base de données spatiales	R-arbre R+ tree (en) R* tree (en) X-tree (en) M-tree (en) arbre de segments Hilbert R-tree (en) Priority R-tree (en)
Autres arbres	Arbre de Merkle Arbre couvrant de poids minimal Arbre syntaxique Arbre de la syntaxe abstraite Finger tree (en) Order statistic tree (en) Arbre métrique Cover tree (en) BK-tree (en) Doubly chained tree iDistance (en) Link-cut tree (en) Fenwick tree (en) Tas Tas binomial Tas de Fibonacci Arbre cousu

v · m Structure de données
Type abstrait	Ensemble File File d'attente à double extrémité File de priorité Liste Vecteur Graphe Union-find
Tableau	Buffer circulaire Tableau de bits Table de hachage Vecteur
Chaînage	Liste chaînée Skip list Chaînage XOR
Arbre	Arbre B Arbre binaire de recherche AVL Bicolore Équilibré Splay Tas Binaire Binomial Fibonacci Trie
Graphe	Diagramme de décision binaire