Les arbres de recherche binaires sont une structure de données pour stocker des éléments avec des capacités de recherche rapide. L'idée est simple et ingénieuse: "moins c'est à gauche, plus c'est à droite." C'est là que la simplicité s'arrête et que commencent les questions complexes d'équilibrage d'un arbre pour qu'il ne se transforme pas en une longue branche.
Dans cet article, nous donnerons une définition, énumérerons les règles de placement des éléments dans un arbre rouge-noir, envisagerons un algorithme d'équilibrage et consoliderons ce qui a été dit sur un exemple. Nous étudions ce sujet plus en détail, ainsi que d'autres types d'arbres de recherche binaires dans le cours «Algorithmes pour les développeurs» .
L'arbre rouge-noir est un arbre de recherche binaire auto-équilibré qui garantit une croissance logarithmique de la hauteur de l'arbre à partir du nombre de nœuds et l'exécution rapide des opérations de base de l'arbre de recherche: ajout, suppression et recherche d'un nœud.
L'arbre rouge-noir n'est pas complètement équilibré, à certains endroits sa hauteur peut varier presque deux fois. Une telle hypothèse n'affecte pas asymptotiquement la vitesse de recherche des éléments, mais accélère considérablement le placement de nouveaux éléments, car vous n'avez pas besoin de "secouer" l'arbre à chaque fois que vous ajoutez des éléments, parfois il suffit d'ajouter simplement un élément rouge sans toucher les autres et sans changer la "hauteur noire" .
Règles pour placer des éléments dans un arbre rouge-noir
- Chaque nœud est rouge ou noir; les feuilles NIL sont toujours noires.
- La racine de l'arbre est toujours noire
- Les deux descendants de chaque nœud rouge sont noirs
- Le chemin vers le bas de n'importe quel nœud à n'importe quelle feuille descendante contient le même nombre de nœuds noirs.
Lorsque vous insérez un nouvel élément, une couleur rouge lui est affectée. Pour remplir les deux premières règles, repeignez simplement les nouveaux sommets dans la couleur souhaitée.
Considérez les règles d'équilibrage pour la mise en œuvre de 3 et 4 points.
Dans chaque figure, on suppose que nous avons déjà ajouté un élément X qui viole la règle 3, nous devons changer la structure de l'arborescence afin que la règle 3 soit exécutée et que 4 ne soit pas violée.
Légende des sommets:
- X - un élément ajouté qui viole 3 paragraphe des règles.
- P - article papa X
- G - le grand-père de l'élément X, le père de l'élément P
- U est l'oncle de l'élément X, le frère de l'élément P, le deuxième fils de l'élément G.
Premier cas - Oncle rouge
Si le père et l'oncle sont tous les deux rouges, nous pouvons alors «abaisser» la couleur noire du niveau du grand-père au niveau du père et repeindre les nœuds, comme le montre la figure. Dans ce cas, la "hauteur noire" restera la même, cependant, la violation de la règle 3 pour l'élément G est possible, par conséquent, il est nécessaire d'appeler récursivement un équilibrage supplémentaire pour ce nœud.
Deuxième cas - un oncle noir - papa et grand-père dans des directions différentes.
Cette structure doit être amenée au troisième cas, lorsque papa et grand-père vont dans la même direction. Pour ce faire, vous devez faire un petit tour du fils X à son père (les règles des tours ne sont pas prises en compte dans cet article) et appeler 3 cas pour l'élément R.
Troisième cas - Oncle noir - Papa et grand-père du même côté
Dans ce cas, on peut déjà faire un grand tour de père en grand-père en oncle noir et repeindre P en noir et G en rouge. À la suite de cette rotation, la règle des 3 sera satisfaite.
Assurez-vous que la 4ème règle est également satisfaite. Supposons qu'avant le grand virage, la hauteur noire de l'élément G était N + 2. La hauteur des éléments "suspendus" sera alors la suivante:
A = N + 1,
B = N + 1,
C = N + 1,
D = N
E = N.
Voyez par vous-même qu'après avoir tourné la règle des 4, c'est vrai pour tous les éléments.
Exemple concret
Nous allons maintenant considérer le processus de formation d'un arbre rouge-noir avec insertion séquentielle des éléments 1, 2, 3, 4, 5 et 6.
Puisque l'élément 1 est la racine, nous le repeignons simplement pour respecter la règle 1.
Après avoir ajouté l'élément 2, toutes les règles sont exécutées.
Lors de l'ajout de l'élément 3, nous avons violé la règle 3. Puisque nous avons un oncle noir, un grand-père et un père d'une part, nous utilisons le troisième cas - nous faisons un tour et repeignons.
Lors de l'ajout de l'élément 4, nous avons de nouveau violé la règle 3. Cette fois, notre oncle est rouge, nous appliquons donc le premier cas avec repeindre - la hauteur noire de l'arbre augmentera de 1. Veuillez noter. que l'algorithme d'équilibrage est lancé en plus pour le grand-père - élément 2, qui, comme la racine, est simplement repeint en noir.
Lors de l'insertion de l'élément 5, nous appliquons à nouveau le cas 3 - nous faisons un grand tour et repeignons les sommets. Notez que la hauteur du noir n'a pas changé.
Lors de l'ajout de l'élément 6, nous avons de nouveau violé la règle 3. Puisque notre oncle est rouge, nous appliquons le premier cas avec repeindre, la hauteur noire n'a pas changé. L'appel d'équilibrage pour 4 éléments n'a rien changé dans l'arborescence, car cet élément ne viole pas les règles.
Ainsi, nous nous sommes familiarisés avec les problèmes d'équilibrage de l'arbre rouge-noir, plus en détail et avec des exemples d'algorithmes sur ce sujet, ainsi que des variétés d'autres arbres de recherche binaires, nous considérons dans le cours
"Algorithmes pour les développeurs" .