Arbre rouge-noir

En informatique , un arbre rouge-noir est une structure de données d'arbre de recherche binaire auto-équilibrée , connue pour son stockage et sa récupération rapides d'informations ordonnées. Les nœuds d'un arbre rouge-noir contiennent un bit de « couleur » supplémentaire, souvent dessiné en rouge et noir, qui permet de garantir que l'arbre est toujours approximativement équilibré.

Lorsque l'arbre est modifié, le nouvel arbre est réorganisé et « repeint » pour restaurer les propriétés de coloration qui limitent le degré de déséquilibre de l'arbre dans le pire des cas. Les propriétés sont conçues de manière à ce que ce réagencement et cette recoloration puissent être effectués efficacement.

Le (ré)équilibrage n'est pas parfait, mais garantit une recherche dans le temps, où se trouve le nombre d'entrées dans l'arbre. Les opérations d'insertion et de suppression, ainsi que le réarrangement et la recoloration de l'arbre, s'exécutent également dans le temps.

Le suivi de la couleur de chaque nœud ne nécessite qu'un seul bit d'information par nœud car il n'y a que deux couleurs (en raison de l'alignement de la mémoire présent dans certains langages de programmation, la consommation réelle de mémoire peut différer). L'arbre ne contient aucune autre donnée spécifique au fait qu'il s'agit d'un arbre rouge-noir, son empreinte mémoire est donc presque identique à celle d'un arbre de recherche binaire classique (non coloré) . Dans certains cas, le bit d'information ajouté peut être stocké sans coût mémoire supplémentaire.

En 1972, Rudolf Bayer a inventé une structure de données qui était un cas particulier d'ordre 4 d'un arbre B. Ces arbres conservaient tous les chemins de la racine à la feuille avec le même nombre de nœuds, créant ainsi des arbres parfaitement équilibrés. Cependant, il ne s'agissait pas d'arbres de recherche binaire . Bayer les a appelés « arbres B binaires symétriques » dans son article et ils sont devenus plus tard populaires sous le nom d'arbres 2–3–4 ou même d'arbres 2–3.

Dans un article de 1978, « A Dichromatic Framework for Balanced Trees », Leonidas J. Guibas et Robert Sedgewick ont ​​dérivé l'arbre rouge-noir de l'arbre binaire symétrique B-tree. La ​​couleur « rouge » a été choisie parce qu'elle était la plus belle couleur produite par l'imprimante laser couleur dont disposaient les auteurs lorsqu'ils travaillaient au Xerox PARC . Une autre réponse de Guibas indique que c'était à cause des stylos rouges et noirs dont ils disposaient pour dessiner les arbres.

En 1993, Arne Andersson a introduit l'idée d'un arbre penché à droite pour simplifier les opérations d'insertion et de suppression.

En 1999, Chris Okasaki a montré comment rendre l'opération d'insertion purement fonctionnelle. Sa fonction d'équilibrage ne devait prendre en charge que 4 cas non équilibrés et un cas équilibré par défaut.

L'algorithme d'origine utilisait 8 cas non équilibrés, mais Cormen et al. (2001) ont réduit ce nombre à 6 cas non équilibrés. Sedgewick a montré que l'opération d'insertion peut être implémentée en seulement 46 lignes de code Java . En 2008, Sedgewick a proposé l' arbre rouge-noir penché à gauche , en s'appuyant sur l'idée d'Andersson qui simplifiait les opérations d'insertion et de suppression. Sedgewick autorisait à l'origine les nœuds dont les deux enfants sont rouges, ce qui rendait ses arbres plus semblables à des arbres 2-3-4, mais plus tard cette restriction a été ajoutée, ce qui rendait les nouveaux arbres plus semblables à des arbres 2-3. Sedgewick a implémenté l'algorithme d'insertion en seulement 33 lignes, ce qui a considérablement raccourci ses 46 lignes de code d'origine.

Un arbre rouge-noir est un type particulier d' arbre de recherche binaire , utilisé en informatique pour organiser des éléments de données comparables , tels que des fragments de texte ou des nombres (comme par exemple les nombres des figures 1 et 2). Les nœuds transportant des clés et/ou des données sont souvent appelés « nœuds internes » , mais pour rendre cela très spécifique, ils sont également appelés nœuds non-NIL dans cet article.

Les nœuds feuilles des arbres rouge-noir ( NIL dans la figure 1) ne contiennent pas de clés ou de données. Ces « feuilles » n'ont pas besoin d'être des individus explicites dans la mémoire de l'ordinateur : un pointeur NULL peut, comme dans toutes les structures de données d'arbre binaire, coder le fait qu'il n'y a pas de nœud enfant à cette position dans le nœud (parent). Néanmoins, par leur position dans l'arbre, ces objets sont en relation avec d'autres nœuds pertinents pour la structure RB, ils peuvent avoir un nœud parent, frère (c'est-à-dire l'autre enfant du parent), oncle, voire neveu ; et peuvent être enfant, mais jamais parent, d'un autre nœud. Il n'est pas vraiment nécessaire d'attribuer une « couleur » à ces objets de fin de chemin, car la condition « est ou » est impliquée par la condition « est » (voir aussi cette remarque).   NILBLACKNIL

La figure 2 montre le même arbre rouge-noir conceptuellement sans ces feuilles NIL. Pour arriver à la même notion de chemin , il faut remarquer que par exemple, 3 chemins passent par le nœud 1 , à savoir un chemin passant par 1 _{à gauche} plus 2 chemins ajoutés passant par 1 _{à droite} , à savoir les chemins passant par 6 _{à gauche} et 6 _{à droite} . De cette façon, ces extrémités des chemins sont également des points d'ancrage pour les nouveaux nœuds à insérer, entièrement équivalents aux feuilles NIL de la figure 1.

Au lieu de cela, pour économiser une quantité marginale de temps d'exécution, ces feuilles NIL (éventuellement nombreuses) peuvent être implémentées comme des pointeurs vers un nœud sentinelle unique (et noir) (au lieu de pointeurs de valeur NULL ).

En conclusion, le fait qu'un enfant n'existe pas (n'est pas un vrai nœud, ne contient pas de données) peut dans tous les cas être spécifié par le même pointeur NULL ou par le même pointeur vers un nœud sentinelle. Dans cet article, l'un ou l'autre choix est appelé nœud NIL et a la valeur constante NIL .

La profondeur noire d'un nœud est définie comme le nombre de nœuds noirs de la racine à ce nœud (c'est-à-dire le nombre d'ancêtres noirs). La hauteur noire d'un arbre rouge-noir est le nombre de nœuds noirs dans tout chemin de la racine aux feuilles, qui, selon l'exigence 4, est constant (alternativement, elle pourrait être définie comme la profondeur noire de tout nœud feuille). La hauteur noire d'un nœud est la hauteur noire du sous-arbre enraciné par lui. Dans cet article, la hauteur noire d'un nœud NIL doit être définie à 0, car son sous-arbre est vide comme suggéré par la figure 2, et sa hauteur d'arbre est également de 0.

En plus des exigences imposées à un arbre de recherche binaire, les éléments suivants doivent être satisfaits par un arbre rouge-noir :

1. Chaque nœud est soit rouge soit noir.
2. Tous les nœuds NIL (figure 1) sont considérés comme noirs.
3. Un nœud rouge n’a pas d’enfant rouge.
4. Chaque chemin d'un nœud donné vers l'un de ses nœuds NIL descendants passe par le même nombre de nœuds noirs.
5. (Conclusion) Si un nœud N a exactement un enfant, l'enfant doit être rouge, car s'il était noir, ses descendants NIL seraient situés à une profondeur noire différente de celle de l'enfant NIL de N , violant ainsi l'exigence 4.

Certains auteurs, par exemple Cormen et al., affirment que « la racine est noire » est la cinquième exigence ; mais pas Mehlhorn et Sanders ou Sedgewick et Wayne. Étant donné que la racine peut toujours être changée du rouge au noir, cette règle a peu d'effet sur l'analyse. Cet article l'omet également, car elle perturbe légèrement les algorithmes et les preuves récursives.

À titre d’exemple, tout arbre binaire parfait composé uniquement de nœuds noirs est un arbre rouge-noir.

Les opérations en lecture seule, telles que la recherche ou le parcours d'arbre, n'affectent aucune des exigences. En revanche, les opérations de modification insert et delete maintiennent facilement les exigences 1 et 2, mais en ce qui concerne les autres exigences, un effort supplémentaire doit être fait pour éviter d'introduire une violation de l'exigence 3, appeléeviolation rouge , ou de l'exigence 4, appeléeviolation noire .

Les exigences imposent une propriété essentielle des arbres rouge-noir : le chemin de la racine à la feuille la plus éloignée n'est pas plus de deux fois plus long que le chemin de la racine à la feuille la plus proche . Le résultat est que l'arbre est équilibré en hauteur . Étant donné que les opérations telles que l'insertion, la suppression et la recherche de valeurs nécessitent un temps dans le pire des cas proportionnel à la hauteur de l'arbre, cette limite supérieure de la hauteur permet aux arbres rouge-noir d'être efficaces dans le pire des cas, à savoir logarithmiques en nombre d'entrées, c'est-à-dire , ce qui n'est pas le cas pour les arbres de recherche binaires ordinaires . Pour une preuve mathématique, voir la section Preuve des limites.

Les arbres rouge-noir, comme tous les arbres binaires de recherche , permettent un accès séquentiel assez efficace (par exemple, un parcours dans l'ordre , c'est-à-dire dans l'ordre gauche-racine-droite) de leurs éléments. Mais ils prennent également en charge un accès direct asymptotiquement optimal via un parcours de la racine à la feuille, ce qui entraîne un temps de recherche plus long.

Les arbres rouge-noir ont une structure similaire aux arbres 2-3-4 , qui sont des arbres B d'ordre 4. Dans les arbres 2-3-4, chaque nœud peut contenir entre 1 et 3 valeurs et avoir entre 2 et 4 enfants. Ces nœuds 2-3-4 correspondent aux groupes nœud noir-enfants rouges dans les arbres rouge-noir, comme le montre la figure 3. Il ne s'agit pas d'une correspondance biunivoque , car les nœuds 3 ont deux représentations équivalentes : l'enfant rouge peut se trouver soit à gauche, soit à droite. La variante d'arbre rouge-noir penchée vers la gauche rend cette relation exactement biunivoque, en n'autorisant que la représentation de l'enfant gauche. Étant donné que chaque nœud 2-3-4 a un nœud noir correspondant, l'invariant 4 des arbres rouge-noir équivaut à dire que les feuilles d'un arbre 2-3-4 se trouvent toutes au même niveau.

Malgré les similitudes structurelles, les opérations sur les arbres rouge-noir sont plus économiques que les arbres B. Les arbres B nécessitent la gestion de vecteurs de longueur variable, tandis que les arbres rouge-noir sont simplement des arbres binaires.

Les arbres rouge-noir offrent des garanties de pire cas pour le temps d'insertion, le temps de suppression et le temps de recherche. Cela les rend non seulement précieux dans les applications sensibles au temps telles que les applications en temps réel , mais aussi précieux dans d'autres structures de données qui offrent des garanties de pire cas. Par exemple, de nombreuses structures de données utilisées en géométrie computationnelle sont basées sur des arbres rouge-noir, et le Completely Fair Scheduler et l'appel système epoll du noyau Linux utilisent des arbres rouge-noir. L' arbre AVL est une autre structure prenant en charge la recherche, l'insertion et la suppression. Les arbres AVL peuvent être colorés en rouge-noir et sont donc un sous-ensemble d'arbres rouge-noir. La hauteur du pire cas d'AVL est de 0,720 fois la hauteur du pire cas des arbres rouge-noir, de sorte que les arbres AVL sont plus rigoureusement équilibrés. Les mesures de performance de Ben Pfaff avec des cas de test réalistes dans 79 exécutions trouvent des ratios AVL/RB compris entre 0,677 et 1,077, une médiane à 0,947 et une moyenne géométrique à 0,910. Les performances des arbres WAVL se situent entre les arbres AVL et les arbres rouge-noir.

Les arbres rouge-noir sont également particulièrement utiles en programmation fonctionnelle , où ils constituent l'une des structures de données persistantes les plus courantes , utilisées pour construire des tableaux et des ensembles associatifs qui peuvent conserver les versions précédentes après des mutations. La version persistante des arbres rouge-noir nécessite de l'espace pour chaque insertion ou suppression, en plus du temps.

Pour chaque arbre 2–3–4 , il existe des arbres rouge–noir correspondants avec des éléments de données dans le même ordre. Les opérations d'insertion et de suppression sur les arbres 2–3–4 sont également équivalentes aux inversions de couleur et aux rotations dans les arbres rouge–noir. Cela fait des arbres 2–3–4 un outil important pour comprendre la logique derrière les arbres rouge–noir, et c'est pourquoi de nombreux textes d'introduction aux algorithmes introduisent les arbres 2–3–4 juste avant les arbres rouge–noir, même si les arbres 2–3–4 ne sont pas souvent utilisés dans la pratique.

En 2008, Sedgewick a introduit une version simplifiée de l'arbre rouge-noir appelé arbre rouge-noir penché à gauche en éliminant un degré de liberté précédemment non spécifié dans l'implémentation. Le LLRB maintient un invariant supplémentaire selon lequel tous les liens rouges doivent pencher à gauche, sauf pendant les insertions et les suppressions. Les arbres rouge-noir peuvent être rendus isométriques soit à 2–3 arbres , soit à 2–3–4 arbres, pour toute séquence d'opérations. L'isométrie de l'arbre 2–3–4 a été décrite en 1978 par Sedgewick. Avec les arbres 2–3–4, l'isométrie est résolue par un « retournement de couleur », correspondant à une division, dans laquelle la couleur rouge de deux nœuds enfants quitte les enfants et se déplace vers le nœud parent.

La description originale de l' arbre tango , un type d'arbre optimisé pour les recherches rapides, utilise spécifiquement des arbres rouge-noir dans le cadre de sa structure de données.

Depuis Java 8, le HashMap a été modifié de telle sorte qu'au lieu d'utiliser une LinkedList pour stocker différents éléments avec des codes de hachage en collision , un arbre rouge-noir est utilisé. Cela se traduit par une amélioration de la complexité temporelle de la recherche d'un tel élément de à où est le nombre d'éléments avec des codes de hachage en collision.

Les opérations en lecture seule, telles que la recherche ou le parcours d'arbre, sur un arbre rouge-noir ne nécessitent aucune modification par rapport à celles utilisées pour les arbres de recherche binaires , car chaque arbre rouge-noir est un cas particulier d'arbre de recherche binaire simple. Cependant, le résultat immédiat d'une insertion ou d'une suppression peut violer les propriétés d'un arbre rouge-noir, dont la restauration est appelée rééquilibrage de sorte que les arbres rouge-noir deviennent auto-équilibrés. Il faut dans le pire des cas un petit nombre, en notation Big O , où est le nombre d'objets dans l'arbre, en moyenne ou amorti , un nombre constant, de changements de couleur (qui sont très rapides en pratique) ; et pas plus de trois rotations de l'arbre (deux pour l'insertion).

Si l’exemple d’implémentation ci-dessous ne convient pas, d’autres implémentations avec explications peuvent être trouvées dans la bibliothèque C annotée de Ben Pfaff GNU libavl (v2.0.3 en date de juin 2019).

Les détails des opérations d'insertion et de suppression seront démontrés avec un exemple de code C++ , qui utilise les définitions de type, les macros ci-dessous et la fonction d'assistance pour les rotations :

// Définitions de type de base :
enum color_t { NOIR , ROUGE };
struct RBnode { // nœud de l'arbre rouge-noir RBnode * parent ; // == NIL si la racine de l'arbre RBnode * child [ 2 ]; // == NIL si child est vide // L'index est : // LEFT := 0, if (key < parent->key) // RIGHT := 1, if (key > parent->key) enum color_t color ; int key ; };
#define NIL NULL // pointeur nul ou pointeur vers le nœud sentinelle 
#define LEFT 0 
#define RIGHT 1 
#define left child[LEFT] 
#define right child[RIGHT]
struct RBtree { // arbre rouge-noir RBnode * root ; // == NIL si l'arbre est vide };
// Obtenir la direction de l'enfant (∈ { GAUCHE, DROITE }) 
// du RBnode non-racine non-NIL* N: 
#define childDir(N) ( N == (N->parent)->droite ? DROITE : GAUCHE )

RBnode * RotateDirRoot ( RBtree * T , // arbre rouge-noir RBnode * P , // racine du sous-arbre ( peut être la racine de T ) int dir ) { // dir ∈ { GAUCHE, DROITE } RBnode * G = P -> parent ; RBnode * S = P -> child [ 1 - dir ]; RBnode * C ; assert ( S != NIL ); // pointeur vers le vrai nœud requis C = S -> child [ dir ]; P -> child [ 1 - dir ] = C ; if ( C != NIL ) C -> parent = P ; S -> child [ dir ] = P ; P -> parent = S ; S -> parent = G ; if ( G != NULL ) G -> child [ P == G -> right ? RIGHT : LEFT ] = S ; else T -> root = S ; return S ; // nouvelle racine du sous-arbre }
#define RotateDir(N,dir) RotateDirRoot(T,N,dir) 
#define RotateLeft(N) RotateDirRoot(T,N,GAUCHE) 
#define RotateRight(N) RotateDirRoot(T,N,DROITE)

La proposition décompose à la fois l'insertion et la suppression (sans mentionner certains cas très simples) en six constellations de nœuds, d'arêtes et de couleurs, qui sont appelés cas. La proposition contient pour les deux cas, l'insertion et la suppression, exactement un cas qui avance d'un niveau noir plus près de la racine et boucle, les cinq autres cas rééquilibrent l'arbre de leur propre chef. Les cas les plus compliqués sont représentés dans un diagramme.

• symbolise un nœud rouge etun nœud noir (non NIL) (de hauteur noire ≥ 1),symbolise la couleur rouge ou noire d'un nœud non NIL, mais la même couleur dans tout le même diagramme. Les nœuds NIL ne sont pas représentés dans les diagrammes.
• La variable N désigne le nœud actuel, qui est étiqueté N ou N dans les diagrammes.    
• Un diagramme contient trois colonnes et deux à quatre actions. La colonne de gauche montre la première itération, la colonne de droite les itérations supérieures, la colonne du milieu montre la segmentation d'un cas en ses différentes actions.

1. L'action « entry » montre la constellation de nœuds avec leurs couleurs qui définissent un cas et enfreignent en grande partie certaines exigences.
   Une bordure bleue entoure le nœud actuel N et les autres nœuds sont étiquetés en fonction de leur relation avec N .
2. Si une rotation est considérée comme utile, cela est illustré dans l'action suivante, qui est intitulée « rotation ».
3. Si une recoloration est jugée utile, elle est illustrée dans l'action suivante, qui est étiquetée « couleur ».
4. Si une réparation est encore nécessaire, les cas utilisent le code d'autres cas et ce après une réaffectation du nœud actuel N , qui porte alors à nouveau un anneau bleu et par rapport auquel d'autres nœuds doivent également être réaffectés. Cette action est appelée "réaffectation".
   Pour les deux cas, insertion et suppression, il existe (exactement) un cas qui itère un niveau noir plus près de la racine ; la constellation réaffectée satisfait alors l'invariant de boucle respectif.

• Un triangle éventuellement numéroté avec un cercle noir au sommetreprésente un sous-arbre rouge-noir (connecté à son parent selon l'exigence 3) avec une hauteur noire égale au niveau d'itération moins un, c'est-à-dire zéro à la première itération. Sa racine peut être rouge ou noire.
  Un triangle éventuellement numérotéreprésente un sous-arbre rouge-noir avec une hauteur noire de un de moins, c'est-à-dire que son parent a une hauteur noire de zéro dans la deuxième itération.

Remarque

Pour plus de simplicité, l'exemple de code utilise la disjonction :

U == NIL || U->color == BLACK // considered black

et la conjonction :

U != NIL && U->color == RED // not considered black

Il faut donc garder à l'esprit que les deux énoncés ne sont pas évalués au total, si U == NIL. Alors dans les deux cas U->colorn'est pas touché (voir Evaluation du court-circuit ).
(Le commentaire considered blackest conforme à l'exigence 2.)

Les déclarations liées ifdoivent apparaître beaucoup moins fréquemment si la proposition est réalisée.

L'insertion commence par le placement du nouveau nœud (non NIL), disons N , à la position dans l' arbre de recherche binaire d'un nœud NIL dont la clé du prédécesseur dans l'ordre est inférieure à la clé du nouveau nœud, qui à son tour est inférieure à la clé de son successeur dans l'ordre. (Souvent, ce positionnement est le résultat d'une recherche dans l'arbre précédant immédiatement l'opération d'insertion et se compose d'un nœud Pavec une direction diravec P->child[dir] == NIL.) Le nœud nouvellement inséré est temporairement coloré en rouge afin que tous les chemins contiennent le même nombre de nœuds noirs qu'avant. Mais si son parent, disons P , est également rouge, cette action introduit une violation rouge.

void RBinsert1 ( RBtree * T , // -> arbre rouge-noir struct RBnode * N , // -> nœud à insérer struct RBnode * P , // -> nœud parent de N (peut être NULL ) int dir ) // côté ( GAUCHE ou DROITE ) de P où insérer N { struct RBnode * G ; // -> nœud parent de P struct RBnode * U ; // -> oncle de N
N -> color = RED ; N -> left = NIL ; N -> right = NIL ; N -> parent = P ; if ( P == NULL ) { // Il n'y a pas de parent T -> root = N ; // N est la nouvelle racine de l'arbre T. return ; // insertion terminée } P -> child [ dir ] = N ; // insère N comme dir-child de P // début de la boucle (do while) : do {

La boucle de rééquilibrage de l'opération d'insertion a l' invariant suivant :

• La variable N , représentant le nœud courant N et initialement le nœud d'insertion, devient la variable parcourant la boucle.
• N est(rouge) au début de chaque itération.
• L'exigence 3 est satisfaite pour toutes les paires nœud←parent avec l'exception possible N ← P lorsque P est également rouge (une violation rouge à N ).
• Toutes les autres propriétés (y compris l’exigence 4) sont satisfaites dans l’ensemble de l’arbre.

• Dans les diagrammes, P est utilisé pour le parent de N , G pour son grand-parent et U pour son oncle. Dans le tableau, un signe — indique la racine.
• Les diagrammes montrent le nœud parent P comme l'enfant gauche de son parent G même s'il est possible que P soit de chaque côté. L'exemple de code couvre les deux possibilités au moyen de la variable side dir.
• Les diagrammes montrent également les cas où P est rouge, la violation du rouge.
• La colonne x indique le changement de direction de l'enfant, c'est-à-dire que o (pour « extérieur ») signifie que P et N sont tous deux des enfants gauches ou droits, tandis que i (pour « intérieur ») signifie que la direction de l'enfant passe de P à N.
• Le groupe de colonnes précédent définit le cas, dont le nom est donné dans la colonne case . Ainsi, les valeurs possibles dans les cellules laissées vides sont ignorées. Ainsi, dans le cas I2, l'exemple de code couvre les deux possibilités de directions enfants de N , bien que le diagramme correspondant n'en montre qu'une seule.
• Les lignes du synopsis sont ordonnées de telle sorte que la couverture de tous les cas RB possibles soit facilement compréhensible.
• La rotation de la colonne indique si une rotation contribue au rééquilibrage.
• L' affectation de colonne montre une affectation de N avant d'entrer dans une étape suivante. Cela induit éventuellement une réaffectation des autres nœuds P , G , U également.
• Si quelque chose a été modifié par le dossier, cela est indiqué dans le groupe de colonnes après .
• Un signe ✓ dans la colonne suivante signifie que le rééquilibrage est terminé avec cette étape. Si la colonne suivante détermine exactement un cas, ce cas est donné comme le cas suivant, sinon il y a des points d'interrogation.
• La boucle est contenue dans les sections « Insérer le cas I1 » et « Insérer le cas I2 », où dans le cas I2 le problème de rééquilibrage est une escalade de niveaux d'arbre ou un niveau noir plus haut dans l'arbre, dans la mesure où le grand-père G devient le nouveau nœud courant N . Il faut donc un maximum d'étapes d'itération pour réparer l'arbre (où est la hauteur de l'arbre). Comme la probabilité d'escalade diminue de manière exponentielle à chaque étape, le coût total de rééquilibrage est constant en moyenne, voire constant amorti.
• À partir du corps de la boucle, le cas I1 sort de lui-même et il existe des branches sortantes vers les cas I4, I6, I5 + I6 et I3.
• Les rotations se produisent dans les cas I6 et I5 + I6 – en dehors de la boucle. Par conséquent, au plus deux rotations se produisent au total.

Le parent P du nœud actuel est noir, donc l'exigence 3 est respectée. L'exigence 4 est également respectée selon l'invariant de boucle.

if ( P -> color == BLACK ) { // Case_I1 (P black): return ; // insertion terminée } // A partir de maintenant P est rouge. if (( G = P -> parent ) == NULL ) goto Case_I4 ; // P red et root // else: P red et G!=NULL. dir = childDir ( P ); // le côté du parent G sur lequel le nœud P est situé U = G -> child [ 1 - dir ]; // oncle if ( U == NIL || U -> color == BLACK ) // considéré comme noir goto Case_I56 ; // P red && U black

Si le parent P et l'oncle U sont tous les deux rouges, alors ils peuvent tous les deux être repeints en noir et le grand-parent G devient rouge pour respecter l'exigence 4. Puisque tout chemin à travers le parent ou l'oncle doit passer par le grand-parent, le nombre de nœuds noirs sur ces chemins n'a pas changé. Cependant, le grand-parent G peut maintenant violer l'exigence 3, s'il a un parent rouge. Après avoir réétiqueté G en N, l'invariant de boucle est satisfait de sorte que le rééquilibrage peut être itéré sur un niveau noir (= 2 niveaux d'arbre) plus haut.

// Case_I2 (P+U rouge) : 
P -> couleur = NOIR ; U -> couleur = NOIR ; G -> couleur = ROUGE ; N = G ; // nouveau nœud actuel // itérer 1 niveau de noir plus haut // (= 2 niveaux d'arbre) } while (( P = N -> parent ) != NULL ); // fin de la boucle (do while)

Le cas d'insertion I2 a été exécuté fois et la hauteur totale de l'arbre a augmenté de 1, étant maintenant Le nœud actuel N est la racine (rouge) de l'arbre et toutes les propriétés RB sont satisfaites.

// Sortie de la boucle (do while) (après avoir échoué depuis le cas_I2). 
// Cas_I3 : N est la racine et rouge. return ; // insertion terminée

Le parent P est rouge ainsi que la racine. Comme N est également rouge, l'exigence 3 est violée. Mais après avoir changé la couleur de P , l'arbre est en forme RB. La hauteur noire de l'arbre augmente de 1.

Case_I4 : // P est la racine et rouge : P -> couleur = NOIR ; retour ; // insertion terminée

Le parent P est rouge mais l'oncle U est noir. Le but ultime est de faire pivoter le nœud parent P vers la position de grand-parent, mais cela ne fonctionnera pas si N est un petit-enfant « interne » de G (c'est-à-dire si N est l'enfant gauche de l'enfant droit de G ou l'enfant droit de l'enfant gauche de G ). Une dirrotation en P inverse les rôles du nœud actuel N et de son parent P. La rotation ajoute des chemins à travers N (ceux du sous-arbre étiqueté 2 , voir le diagramme) et supprime des chemins à travers P (ceux du sous-arbre étiqueté 4 ). Mais P et N sont tous deux rouges, donc l'exigence 4 est préservée. L'exigence 3 est restaurée dans le cas 6.

Case_I56 : // P rouge && U noir : if ( N == P -> child [ 1 - dir ]) { // Case_I5 (P rouge && U noir && N petit-enfant interne de G) : RotateDir ( P , dir ); // P n'est jamais la racine N = P ; // nouveau nœud actuel P = G -> child [ dir ]; // nouveau parent de N // passe à Case_I6 }

Le nœud actuel N est maintenant certain d'être un petit-enfant « externe » de G (à gauche de l'enfant gauche ou à droite de l'enfant droit). Maintenant, (1-dir)faites une rotation à G , en mettant P à la place de G et en faisant de P le parent de N et G. G est noir et son ancien enfant P est rouge, car l'exigence 3 a été violée. Après avoir échangé les couleurs de P et G, l'arbre résultant satisfait l'exigence 3. L'exigence 4 reste également satisfaite, car tous les chemins qui passaient par le G noir passent maintenant par le P noir .

// Case_I6 (P rouge && U noir && N petit-enfant extérieur de G) : 
RotateDirRoot ( T , G , 1 - dir ); // G peut être la racine P -> couleur = NOIR ; G -> couleur = ROUGE ; retour ; // insertion terminée } // fin de RBinsert1

Parce que l'algorithme transforme l'entrée sans utiliser de structure de données auxiliaire et en utilisant seulement une petite quantité d'espace de stockage supplémentaire pour les variables auxiliaires, il est sur place .

- Lorsque le nœud supprimé a 2 enfants (non NIL), nous pouvons alors échanger sa valeur avec son successeur dans l'ordre (l'enfant le plus à gauche du sous-arbre de droite), puis supprimer le successeur à la place. Étant donné que le successeur est le plus à gauche, il ne peut avoir qu'un enfant à droite (non NIL) ou aucun enfant du tout.

- Lorsque le nœud supprimé n'a qu'un seul enfant (non NIL). Dans ce cas, remplacez simplement le nœud par son enfant et colorez-le en noir.
L'enfant unique (non NIL) doit être rouge conformément à la conclusion 5 et le nœud supprimé doit être noir conformément à l'exigence 3.

- Lorsque le nœud supprimé n'a pas d'enfants (tous deux NIL) et est la racine, remplacez-le par NIL. L'arbre est vide.

- Lorsque le nœud supprimé n'a pas d'enfants (tous deux NIL) et est rouge , supprimez simplement le nœud feuille.

- Lorsque le nœud supprimé n'a pas d'enfants (tous deux NIL) et est noir , sa suppression créera un déséquilibre et nécessitera une correction, comme indiqué dans la section suivante.

Le cas complexe est celui où N n'est pas la racine, est coloré en noir et n'a pas d'enfant propre (⇔ seulement des enfants NIL). Dans la première itération, N est remplacé par NIL.

void RBdelete2 ( RBtree * T , // -> arbre rouge–noir struct RBnode * N ) // -> nœud à supprimer { struct RBnode * P = N -> parent ; // -> nœud parent de N octets dir ; // côté de P sur lequel N est situé (∈ { GAUCHE, DROITE }) struct RBnode * S ; // -> frère de N struct RBnode * C ; // -> neveu proche struct RBnode * D ; // -> neveu éloigné
// P != NULL, puisque N n'est pas la racine. 
dir = childDir ( N ​​); // côté du parent P sur lequel se trouve le nœud N // Remplacez N à son parent P par NIL : P -> child [ dir ] = NIL ; goto Start_D ; // sautez dans la boucle
// début de la boucle (do while) : 
do { dir = childDir ( N ​​); // côté du parent P sur lequel le nœud N est situé Start_D : S = P -> child [ 1 - dir ]; // frère de N (a une hauteur noire >= 1) D = S -> child [ 1 - dir ]; // neveu éloigné C = S -> child [ dir ]; // neveu proche if ( S -> color == RED ) goto Case_D3 ; // S red ===> P+C+D black // S est noir : if ( D != NIL && D -> color == RED ) // non considéré comme noir goto Case_D6 ; // D red && S black if ( C != NIL && C -> color == RED ) // non considéré comme noir goto Case_D5 ; // C red && S+D black // Ici les deux neveux sont == NIL (première itération) ou noirs (plus tard). si ( P -> couleur == ROUGE ) aller à Case_D4 ; // P rouge && C+S+D noir

La boucle de rééquilibrage de l'opération de suppression a l' invariant suivant :

• Au début de chaque itération, la hauteur noire de N est égale au numéro d'itération moins un, ce qui signifie que dans la première itération, elle est nulle et que N est un véritable nœud noirdans des itérations supérieures.
• Le nombre de nœuds noirs sur les chemins passant par N est inférieur d'un à celui d'avant la suppression, alors qu'il reste inchangé sur tous les autres chemins, de sorte qu'il y a violation noire en P si d'autres chemins existent.
• Toutes les autres propriétés (y compris l’exigence 3) sont satisfaites dans l’ensemble de l’arbre.

• Dans les diagrammes ci-dessous, P est utilisé pour le parent de N , S pour le frère de N , C (qui signifie neveu proche ) pour l'enfant de S dans la même direction que N , et D (qui signifie neveu éloigné ) pour l'autre enfant de S ( S ne peut pas être un nœud NIL dans la première itération, car il doit avoir une hauteur noire de un, qui était la hauteur noire de N avant sa suppression, mais C et D peuvent être des nœuds NIL).
• Les diagrammes montrent le nœud actuel N comme l'enfant gauche de son parent P même s'il est possible que N soit de chaque côté. Les exemples de code couvrent les deux possibilités au moyen de la variable side dir.
• Au début (dans la première itération) de la suppression, N est le nœud NIL qui remplace le nœud à supprimer. Étant donné que son emplacement dans le nœud parent est la seule chose importante, il est symbolisé par(signifiant : le nœud courant N est un nœud NIL et un enfant de gauche) dans la colonne de gauche des diagrammes de suppression. Au fur et à mesure que l'opération se déroule, des nœuds propres (de hauteur noire ≥ 1) peuvent également devenir courants (voir par exemple le cas D2).
• En comptant les balles noires (et) dans un diagramme de suppression, on peut observer que les chemins passant par N ont une balle de moins que les autres chemins. Cela signifie une violation noire à P — si elle existe.
• La constellation de couleurs dans le groupe de colonnes précédent définit le cas, dont le nom est donné dans la colonne case . Ainsi, les valeurs possibles dans les cellules laissées vides sont ignorées.
• Les lignes du synopsis sont ordonnées de telle sorte que la couverture de tous les cas RB possibles soit facilement compréhensible.
• La rotation de la colonne indique si une rotation contribue au rééquilibrage.
• L' affectation de colonne montre une affectation de N avant d'entrer dans une étape d'itération ultérieure. Cela induit éventuellement une réaffectation des autres nœuds P , C , S , D également.
• Si quelque chose a été modifié par le dossier, cela est indiqué dans le groupe de colonnes après .
• Un signe ✓ dans la colonne suivante signifie que le rééquilibrage est terminé avec cette étape. Si la colonne suivante détermine exactement un cas, ce cas est donné comme le cas suivant, sinon il y a des points d'interrogation.
• La boucle est contenue dans les sections de Start_Dà « Supprimer le cas D2 », où le problème de rééquilibrage est amplifié à un niveau supérieur dans l'arbre dans la mesure où le parent P devient le nouveau nœud courant N . Il faut donc un maximum d'itérations pour réparer l'arbre (où est la hauteur de l'arbre). Étant donné que la probabilité d'escalade diminue de manière exponentielle à chaque itération, le coût total de rééquilibrage est constant en moyenne, voire constant amorti. (En passant : Mehlhorn et Sanders soulignent : « Les arbres AVL ne prennent pas en charge les coûts de mise à jour amortis constants. » Cela est vrai pour le rééquilibrage après une suppression, mais pas pour l'insertion AVL. )
• En dehors du corps de la boucle, il existe des branches sortantes vers les cas D3, D6, D5 + D6, D4 et D1 ; la section « Supprimer le cas D3 » possède elle-même trois branches sortantes différentes vers les cas D6 , D5 et D4 .
• Les rotations se produisent dans les cas D6 et D5 + D6 et D3 + D5 + D6 – tous à l'extérieur de la boucle. Par conséquent, au maximum trois rotations se produisent au total.

Le nœud actuel N est la nouvelle racine. Un nœud noir a été supprimé de chaque chemin, de sorte que les propriétés RB sont préservées. La hauteur noire de l'arbre diminue de 1.

// Case_D1 (P == NULL) : 
retour ; // suppression terminée

Les enfants de P , S et S sont noirs. Après avoir peint S en rouge, tous les chemins passant par S , qui sont précisément les chemins ne passant pas par N , ont un nœud noir de moins. Maintenant, tous les chemins du sous-arbre enraciné par P ont le même nombre de nœuds noirs, mais un de moins que les chemins qui ne passent pas par P , donc l'exigence 4 peut toujours être violée. Après avoir réétiqueté P en N, l'invariant de boucle est satisfait de sorte que le rééquilibrage peut être itéré sur un niveau noir (= 1 niveau d'arbre) plus haut.

// Case_D2 (P+C+S+D noir) : 
S -> couleur = ROUGE ; N = P ; // nouveau nœud courant (peut-être la racine) // itérer 1 niveau noir // (= 1 niveau d'arbre) plus haut } while (( P = N -> parent ) != NULL ); // fin de la boucle (do while) // (avec return;)

Le frère S est rouge, donc P et les neveux C et D doivent être noirs. Une dirrotation en P transforme S en grand-parent de N. Ensuite, après avoir inversé les couleurs de P et S , le chemin à travers N est encore court d'un nœud noir. Mais N a maintenant un parent rouge P et après la réaffectation un frère noir S , donc les transformations dans les cas D4, D5 ou D6 sont capables de restaurer la forme RB.

Case_D3 : // S rouge && P+C+D noir : RotateDirRoot ( T , P , dir ); // P peut être la racine P -> couleur = ROUGE ; S -> couleur = NOIR ; S = C ; // != NIL // maintenant : P rouge && S noir D = S -> enfant [ 1 - dir ]; // neveu éloigné if ( D != NIL && D -> couleur == ROUGE ) goto Case_D6 ; // D rouge && S noir C = S -> enfant [ dir ]; // neveu proche if ( C != NIL && C -> couleur == ROUGE ) goto Case_D5 ; // C rouge && S+D noir // Sinon, C+D sont considérés comme noirs. // passer à Case_D4

Les enfants de S et S sont noirs, mais P est rouge. L'échange des couleurs de S et P n'affecte pas le nombre de nœuds noirs sur les chemins passant par S , mais ajoute un au nombre de nœuds noirs sur les chemins passant par N , compensant ainsi le nœud noir supprimé sur ces chemins.

Case_D4 : // P rouge && S+C+D noir : S -> couleur = ROUGE ; P -> couleur = NOIR ; retour ; // suppression terminée

Le frère S est noir, l'enfant proche de S , C , est rouge et l'enfant éloigné de S, D, est noir. Après une (1-dir)rotation en S, le neveu C devient le parent de S et le nouveau frère de N. Les couleurs de S et C sont échangées. Tous les chemins ont toujours le même nombre de nœuds noirs, mais N a maintenant un frère noir dont l'enfant éloigné est rouge, donc la constellation est adaptée au cas D6. Ni N ni son parent P ne sont affectés par cette transformation, et P peut être rouge ou noir (dans le diagramme).

Case_D5 : // C rouge && S+D noir : RotateDir ( S , 1 - dir ); // S n'est jamais la racine S -> couleur = ROUGE ; C -> couleur = NOIR ; D = S ; S = C ; // maintenant : D rouge && S noir // passer à Case_D6

Le frère S est noir, le fils éloigné de S D est rouge. Après une dirrotation en P, le frère S devient le parent de P et du fils éloigné de S D . Les couleurs de P et S sont échangées, et D devient noir. L'ensemble du sous-arbre a toujours la même couleur à sa racine S , à savoir soit rouge soit noir (dans le diagramme), qui fait référence à la même couleur avant et après la transformation. De cette façon, l'exigence 3 est préservée. Les chemins du sous-arbre ne passant pas par N (c'est-à-dire passant par D et le nœud 3 dans le diagramme) passent par le même nombre de nœuds noirs qu'avant, mais N a maintenant un ancêtre noir supplémentaire : soit P est devenu noir, soit il était noir et S a été ajouté comme grand-parent noir. Ainsi, les chemins passant par N passent par un nœud noir supplémentaire, de sorte que l'exigence 4 est rétablie et l'arbre total est en forme RB.

Case_D6 : // D rouge && S noir : RotateDirRoot ( T , P , dir ); // P peut être la racine S -> couleur = P -> couleur ; P -> couleur = NOIR ; D -> couleur = NOIR ; retour ; // suppression terminée } // fin de RBdelete2

Parce que l'algorithme transforme l'entrée sans utiliser de structure de données auxiliaire et en utilisant seulement une petite quantité d'espace de stockage supplémentaire pour les variables auxiliaires, il est sur place .

Car il y a un arbre rouge-noir de grande taille avec

nœuds ( est la fonction de plancher ) et il n'y a pas d'arbre rouge-noir de cette hauteur d'arbre avec moins de nœuds - donc il est minimal . Sa hauteur noire est     (avec une racine noire) ou pour impair (alors avec une racine rouge) également  

Preuve

Pour qu'un arbre rouge-noir d'une certaine hauteur ait un nombre minimal de nœuds, il doit avoir exactement un chemin le plus long avec un nombre maximal de nœuds rouges, pour atteindre une hauteur d'arbre maximale avec une hauteur noire minimale. Outre ce chemin, tous les autres nœuds doivent être noirs. Si un nœud est retiré de cet arbre, il perd soit de la hauteur, soit une propriété RB.

L'arbre RB de hauteur à racine rouge est minimal. Ceci est en accord avec

Un arbre RB minimal (RB _h dans la figure 4) de hauteur a une racine dont les deux sous-arbres enfants sont de hauteur différente. Le sous-arbre enfant supérieur est également un arbre RB minimal, RB _{h –1} , contenant également un chemin le plus long qui définit sa hauteur ; il a des nœuds et la hauteur noire. L'autre sous-arbre est un arbre binaire parfait de hauteur (noire) ayant des nœuds noirs et aucun nœud rouge. Le nombre de nœuds est alors déterminé par récurrence.$1h>1$1}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3df33213a54649226c03c8115b130c49170d0683">

Le graphique de la fonction est convexe et linéaire par morceaux avec des points d'arrêt où La fonction a été tabulée comme A027383( h –1) pour (séquence A027383 dans l' OEIS ).

Résoudre la fonction pour

L'inégalité conduit à , ce qui pour impair conduit à $8=2^\{39>8=2^3$8=2^{3}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fc6aa3b743ffc4de7d75d22ec4e30b93ae86037">$2^\{3/23>2^{3/2}$2^{3/2}}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/289041b8c90d373cd5129f1c257ef854de064e4c">

$2\backslash cdot\; 2^\{h/2\}-2m_h=3\cdot 2^{(h-1)/2}-2=(3\cdot 2^{-3/2})\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2$2\cdot 2^{h/2}-2}" data-src="https://wikimedia.org/api/rest_v1/media/math/render/svg/11105813afbd3e754a837dae4eb53795fdf60696">.

Donc dans les deux cas, pair et impair, se trouve dans l'intervalle

avec le nombre de nœuds.

Conclusion

Un arbre rouge-noir avec des nœuds (clés) a une hauteur d'arbre

En plus des opérations d'insertion, de suppression et de recherche d'éléments uniques, plusieurs opérations d'ensemble ont été définies sur les arbres rouge-noir : union , intersection et set difference . Ensuite, des opérations rapides en masse sur les insertions ou les suppressions peuvent être implémentées sur la base de ces fonctions d'ensemble. Ces opérations d'ensemble s'appuient sur deux opérations d'assistance, Split et Join . Avec les nouvelles opérations, l'implémentation des arbres rouge-noir peut être plus efficace et hautement parallélisable. Afin d'atteindre ses complexités temporelles, cette implémentation nécessite que la racine soit autorisée à être rouge ou noire, et que chaque nœud stocke sa propre hauteur noire .

• Joindre : La fonction Join s'appuie sur deux arbres rouge-noir t ₁ et t ₂ et une clé k , où t ₁ < k < t ₂ , c'est-à-dire que toutes les clés de t ₁ sont inférieures à k , et toutes les clés de t ₂ sont supérieures à k . Elle renvoie un arbre contenant tous les éléments de t ₁ , t ₂ également sous la forme k .

Si les deux arbres ont la même hauteur noire, Join crée simplement un nouveau nœud avec le sous-arbre gauche t ₁ , la racine k et le sous-arbre droit t ₂ . Si t ₁ et t ₂ ont tous deux une racine noire, définissez k comme étant rouge. Sinon, k est défini comme étant noir.

Si les hauteurs noires sont inégales, supposons que t ₁ a une hauteur noire plus grande que t ₂ (l'autre cas est symétrique). Join suit la colonne vertébrale droite de t ₁ jusqu'à un nœud noir c , qui est équilibré avec t ₂ . À ce stade, un nouveau nœud avec un enfant gauche c , une racine k (définie comme rouge) et un enfant droit t ₂ est créé pour remplacer c. Le nouveau nœud peut invalider l'invariant rouge-noir car au plus trois nœuds rouges peuvent apparaître d'affilée. Cela peut être résolu avec une double rotation. Si le problème de double rouge se propage à la racine, la racine est alors définie comme noire, restaurant les propriétés. Le coût de cette fonction est la différence des hauteurs noires entre les deux arbres d'entrée.

• Split : Pour diviser un arbre rouge-noir en deux arbres plus petits, ceux plus petits que la clé x et ceux plus grands que la clé x , tracez d'abord un chemin à partir de la racine en insérant x dans l'arbre rouge-noir. Après cette insertion, toutes les valeurs inférieures à x se trouveront à gauche du chemin et toutes les valeurs supérieures à x se trouveront à droite. En appliquant Join , tous les sous-arbres du côté gauche sont fusionnés de bas en haut en utilisant les clés du chemin comme nœuds intermédiaires de bas en haut pour former l'arbre de gauche, et la partie droite est symétrique.

Pour certaines applications, Split renvoie également une valeur booléenne indiquant si x apparaît dans l'arbre. Le coût de Split est de l'ordre de la hauteur de l'arbre. Cet algorithme n'a en fait rien à voir avec les propriétés spéciales d'un arbre rouge-noir et peut être utilisé sur n'importe quel arbre avec une opération de jointure , comme un arbre AVL .

L'algorithme de jointure est le suivant :

fonction joinRightRB(T L , k, T R ): si (T L .color=black) et (T L .blackHeight=T R .blackHeight): renvoie Node(T L ,⟨k,red⟩,T R ) T'=Node(T L .left,⟨T L .key,T L .color⟩,joinRightRB(T L .right,k,T R )) si (T L .color=black) et (T'.right.color=T'.right.right.color=red) : T'.droite.droite.couleur=noir; retourner rotateLeft(T') retourner T' /* T ' '[recte T'] */ fonction joinLeftRB(T L , k, T R ): /* symétrique à joinRightRB */ fonction join(T L , k, T R ): si T L .blackHeight>T R .blackHeight: T'=joinRightRB(T L ,k,T R ) si (T'.color=red) et (T'.right.color=red) : T'.color=noir renvoie T' si T R .blackHeight>T L .blackHeight : /* symétrique */ si (T L .color=black) et (T R .color=black) : renvoie Node(T L ,⟨k,red⟩,T R ) renvoie Node(T L ,⟨k,black⟩,T R ) 

L'algorithme de division est le suivant :

fonction split(T, k) : si (T = nil) renvoie (nil, false, nil) si (k = T.key) renvoie (T.left, true, T.right) si (k < T.key) : (L',b,R') = split(T.gauche, k) retour (L',b,join(R',T.key,T.right)) (L',b,R') = split(T.droite, k) retour (join(T.gauche,T.clé,L'),b,T.droite) 

L'union de deux arbres rouge-noir t ₁ et t ₂ représentant les ensembles A et B , est un arbre rouge-noir t qui représente A ∪ B . La fonction récursive suivante calcule cette union :

fonction union(t 1 , t 2 ): si t 1 = nil renvoie t 2 
si t 2 = nil renvoie t 1 (L 1 ,b,R 1 )=split(t 1 ,t 2 .key) proc1= début : T L = union (L 1 , t 2 . gauche) proc2= démarrer : T R = union (R 1 , t 2. droite) attendre tout proc1, proc2 retourner join (T L , t 2. clé, T R ) 

Ici, split est supposé renvoyer deux arbres : l'un contenant les clés moins sa clé d'entrée, l'autre contenant les clés plus grandes. (L'algorithme est non destructif , mais une version destructive en place existe également.)

L'algorithme d'intersection ou de différence est similaire, mais nécessite la routine d'assistance Join2 qui est la même que Join mais sans la clé du milieu. En fonction des nouvelles fonctions d'union, d'intersection ou de différence, une ou plusieurs clés peuvent être insérées ou supprimées de l'arbre rouge-noir. Étant donné que Split appelle Join mais ne traite pas directement les critères d'équilibrage des arbres rouge-noir, une telle implémentation est généralement appelée implémentation « basée sur la jointure » .

La complexité de chacune des opérations union, intersection et différence est pour deux arbres rouge-noir de tailles et . Cette complexité est optimale en termes de nombre de comparaisons. Plus important encore, étant donné que les appels récursifs à union, intersection ou différence sont indépendants les uns des autres, ils peuvent être exécutés en parallèle avec une profondeur parallèle . Lorsque , l'implémentation basée sur la jointure a le même graphe acyclique dirigé par calcul (DAG) que l'insertion et la suppression d'un seul élément si la racine de l'arbre le plus grand est utilisée pour diviser l'arbre le plus petit.

Les algorithmes parallèles de construction d'arbres rouge-noir à partir de listes triées d'éléments peuvent s'exécuter en temps constant ou en temps, selon le modèle informatique, si le nombre de processeurs disponibles est asymptotiquement proportionnel au nombre d'éléments où . Des algorithmes parallèles de recherche, d'insertion et de suppression rapides sont également connus.

Les algorithmes basés sur la jointure pour les arbres rouge-noir sont parallèles pour les opérations en masse, notamment l'union, l'intersection, la construction, le filtrage, la réduction de carte, etc.

Les opérations de base telles que l'insertion, la suppression ou la mise à jour peuvent être parallélisées en définissant des opérations qui traitent des volumes de plusieurs éléments. Il est également possible de traiter des volumes avec plusieurs opérations de base, par exemple des volumes peuvent contenir des éléments à insérer et également des éléments à supprimer de l'arbre.

Les algorithmes pour les opérations en masse ne s'appliquent pas uniquement à l'arbre rouge-noir, mais peuvent également être adaptés à d'autres structures de données de séquences triées, comme l' arbre 2-3 , l'arbre 2-3-4 et l'arbre (a,b) . Dans ce qui suit, différents algorithmes pour l'insertion en masse seront expliqués, mais les mêmes algorithmes peuvent également être appliqués à la suppression et à la mise à jour. L'insertion en masse est une opération qui insère chaque élément d'une séquence dans un arbre .

Cette approche peut être appliquée à chaque structure de données de séquence triée qui prend en charge des opérations de jointure et de division efficaces. L'idée générale est de diviser en plusieurs parties et d'effectuer les insertions sur ces parties en parallèle.

1. Tout d’abord, la majeure partie des éléments à insérer doit être triée.
2. Après cela, l’algorithme se divise en parties de tailles à peu près égales.
3. Ensuite, l'arbre doit être divisé en parties de manière à ce que pour chaque partie, les contraintes suivantes soient respectées :
4. L'algorithme insère désormais chaque élément de de manière séquentielle. Cette étape doit être effectuée pour chaque , ce qui peut être fait par jusqu'à processeurs en parallèle.
5. Enfin, les arbres obtenus seront joints pour former le résultat final de l’ensemble de l’opération.

Notez qu'à l'étape 3, les contraintes de division garantissent qu'à l'étape 5, les arbres peuvent être à nouveau joints et la séquence résultante est triée.

• 
  arbre initial
• 
  diviser I et T
• 
  insérer dans le T fendu
• 
  articulation

Le pseudo-code montre une implémentation simple de type diviser pour régner de l'algorithme basé sur la jointure pour l'insertion en masse. Les deux appels récursifs peuvent être exécutés en parallèle. L'opération de jointure utilisée ici diffère de la version expliquée dans cet article, à la place, join2 est utilisé, ce qui manque le deuxième paramètre k.

Insérer en vrac (T, I, k) : Je.sort() bulklInsertRec(T, I, k) bulkInsertRec (T, I, k) : si k = 1 : pour tout e dans I : T.insert(e) sinon m := ⌊taille(I) / 2⌋ (T 1 , _, T 2 ) := diviser(T, I[m]) bulkInsertRec(T 1 , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T 1 , T 2 ) 

Le tri n'est pas pris en compte dans cette analyse.

Ceci peut être amélioré en utilisant des algorithmes parallèles pour le fractionnement et la jonction. Dans ce cas, le temps d'exécution est de .

Une autre méthode de parallélisation des opérations en masse consiste à utiliser une approche de pipelining . Cela peut être réalisé en décomposant la tâche de traitement d'une opération de base en une séquence de sous-tâches. Pour plusieurs opérations de base, les sous-tâches peuvent être traitées en parallèle en attribuant chaque sous-tâche à un processeur distinct.

1. Tout d’abord, la majeure partie des éléments à insérer doit être triée.
2. Pour chaque élément de l'algorithme, on localise la position d'insertion correspondante dans . Cela peut être fait en parallèle pour chaque élément car il ne sera pas muté dans ce processus. Il faut maintenant le diviser en sous-séquences en fonction de la position d'insertion de chaque élément. Par exemple, la sous-séquence de contient les éléments dont la position d'insertion serait à gauche du nœud .
3. L'élément central de chaque sous-séquence sera inséré dans comme un nouveau nœud . Cela peut être fait en parallèle pour chaque nœud puisque par définition la position d'insertion de chacun est unique. Si contient des éléments à gauche ou à droite de , ceux-ci seront contenus dans un nouvel ensemble de sous-séquences comme ou .
4. Il est désormais possible de contenir jusqu'à deux nœuds rouges consécutifs à la fin des chemins allant de la racine aux feuilles, qui doivent être réparés. Notez que, lors de la réparation, la position d'insertion des éléments doit être mise à jour si les nœuds correspondants sont affectés par des rotations. Si deux nœuds ont des ancêtres noirs les plus proches différents, ils peuvent être réparés en parallèle. Étant donné qu'au plus quatre nœuds peuvent avoir le même ancêtre noir le plus proche, les nœuds du niveau le plus bas peuvent être réparés en un nombre constant d'étapes parallèles. Cette étape sera appliquée successivement aux niveaux noirs supérieurs jusqu'à ce qu'elle soit entièrement réparée.
   
   
5. Les étapes 3 à 5 seront répétées sur les nouvelles sous-séquences jusqu'à ce que soit vide. À ce stade, tous les éléments ont été insérés. Chaque application de ces étapes est appelée une étape . Étant donné que la longueur des sous-séquences dans est et qu'à chaque étape, les sous-séquences sont coupées en deux, le nombre d'étapes est . Étant donné que toutes les étapes remontent les niveaux noirs de l'arbre, elles peuvent être parallélisées dans un pipeline. Une fois qu'une étape a fini de traiter un niveau noir, l'étape suivante peut monter et continuer à ce niveau.
   

• 
  Arbre initial
• 
  Trouver les positions d'insertion
• 
  Étape 1 : insère des éléments
• 
  L'étape 1 commence à réparer les nœuds
• 
  Étape 2 : insertion d'éléments
• 
  L'étape 2 commence à réparer les nœuds
• 
  Étape 3 : insertion d'éléments
• 
  L'étape 3 commence à réparer les nœuds
• 
  L'étape 3 continue de réparer les nœuds

Le tri n'est pas pris en compte dans cette analyse. De plus, est supposé plus petit que , sinon il serait plus efficace de construire l'arbre résultant à partir de zéro.