Dans le post précédent, nous avons abordé l’introduction aux arbres rouges-noirs. Dans ce post, l’insertion est abordée. Dans l’insertion de l’arbre AVL, nous avons utilisé la rotation comme outil pour faire l’équilibrage après l’insertion. Dans l’arbre Red-Black, nous utilisons deux outils pour faire l’équilibrage.
- Recoloration
- Rotation
La recoloration est le changement de couleur du nœud c’est-à-dire que si celui-ci est rouge, alors on le change en noir et vice versa. Il faut noter que la couleur du nœud NULL est toujours noire. De plus, nous essayons toujours de recolorer d’abord, si le recoloriage ne fonctionne pas, alors nous optons pour la rotation. Voici un algorithme détaillé. Les algorithmes ont principalement deux cas selon la couleur de l’oncle. Si l’oncle est rouge, nous le recolorons. Si l’oncle est noir, on fait des rotations et/ou des recolorations.
La représentation avec laquelle nous allons travailler est :
Cette représentation est basée sur X
Logique:
D’abord, il faut insérer le nœud de manière similaire à celle d’un arbre binaire et lui attribuer une couleur rouge. Maintenant, si le nœud est un nœud racine alors changez sa couleur en noir, mais si ce n’est pas le cas alors vérifiez la couleur du nœud parent. Si sa couleur est noire, ne changez pas la couleur, mais si elle ne l’est pas, c’est-à-dire si elle est rouge, vérifiez la couleur de l’oncle du noeud. Si l’oncle du nœud a une couleur rouge alors changez la couleur du parent et de l’oncle du nœud en noir et celle du grand-père en couleur rouge et répétez le même processus pour lui (c’est-à-dire le grand-père).
Mais, si l’oncle du nœud a une couleur noire alors il y a 4 cas possibles :
- Cas gauche (rotation LL):
- Cas gauche droit (rotation LR) :
- Cas droit droit (rotation RR):
- Cas gauche droit (rotation RL):
Maintenant, après ces rotations, si les couleurs des nœuds ne correspondent pas, alors recolorez-les.
Algorithme:
Laissez x être le nœud nouvellement inséré.
- Exécutez l’insertion BST standard et rendez la couleur des nœuds nouvellement insérés comme ROUGE.
- Si x est la racine, changez la couleur de x comme NOIRE (La hauteur noire de l’arbre complet augmente de 1).
- Faites ce qui suit si la couleur du parent de x n’est pas NOIRE et si x n’est pas la racine.
a) Si l’oncle de x est ROUGE (Le grand-parent doit avoir été noir à partir de la propriété 4)
(i) Changez la couleur du parent et de l’oncle en NOIR.
(ii) Changer la couleur d’un grand-parent en ROUGE.
(iii) Changez x = le grand-parent de x, répétez les étapes 2 et 3 pour le nouveau x.b) Si l’oncle de x est NOIR, alors il peut y avoir quatre configurations pour x, le parent de x (p) et le grand-parent de x (g) (Ceci est similaire à l’arbre AVL)
(i) Cas gauche gauche (p est l’enfant gauche de g et x est l’enfant gauche de p)
(ii) Cas gauche droit (p est l’enfant gauche de g et x est l’enfant gauche de p) enfant gauche de g et x est l’enfant droit de p)
(iii) Cas droit droit (miroir du cas i)
(iv) Cas gauche droit (miroir du cas ii)
Exemple : Création d’un arbre rouge-noir avec les éléments 3, 21, 32 et 17 dans un arbre vide.
Solution :
Lorsque le premier élément est inséré, il est inséré comme un nœud racine et comme le nœud racine a une couleur noire donc il acquiert la couleur noire.
Le nouvel élément est toujours inséré avec une couleur rouge et comme 21 > 3 donc il devient la partie du sous-arbre droit du nœud racine.
Maintenant, comme nous insérons 32, nous voyons qu’il y a une paire père-enfant rouge qui viole la règle de l’arbre rouge-noir, donc nous devons la faire pivoter. En outre, nous voyons les conditions de la rotation RR (considérant le nœud nul du nœud racine comme noir) donc après la rotation comme le nœud racine ne peut pas être Rouge donc nous devons effectuer un recoloriage dans l’arbre résultant dans l’arbre montré ci-dessus.
Maintenant quand nous insérons le nouvel élément le parent et le nœud enfant avec la couleur rouge apparaissent à nouveau et ici nous devons les recolorer. Nous voyons que le nœud parent et le nœud oncle ont tous deux une couleur rouge, donc nous changeons simplement leur couleur en noir et changeons la couleur du grand-père en rouge. Maintenant, comme le grand-père est le nœud racine, nous changeons à nouveau sa couleur en noir, ce qui donne l’arbre montré ci-dessus.
Arborescence finale :
L’arbre final ressemblera à ceci
Veuillez vous référer au programme C pour l’insertion de l’arbre rouge-noir pour la mise en œuvre complète de l’algorithme ci-dessus.
Arbre rouge-noir | Ensemble 3 (Supprimer)