Arbre rouge et noir
Les arbres rouges et noirs sont des arbres qui sont souvent mentionnés dans les structures de données et les algorithmes mais ne peuvent pas être expliqués en détail. Ce sont également des arbres qui sont souvent demandés dans les entretiens techniques. Cependant, que ce soit le matériel dans les livres ou en ligne, ils sont généralement plus rigides et difficiles à comprendre. Pouvez-vous comprendre les arbres rouges et noirs d'une manière plus intuitive? Cet article expliquera les opérations d'insertion et de suppression des arbres rouges et noirs de manière graphique.
L'apprentissage de la structure des arbres est un processus progressif. Les arbres avec lesquels nous entrons généralement en contact sont des arbres binaires. En termes simples, chaque nœud non-feuille a et seulement deux enfants, appelés l'enfant gauche et l'enfant droit. Il existe un type spécial d'arbre dans un arbre binaire appelé arbre de recherche binaire. Un arbre de recherche binaire est un arbre ordonné. Pour chaque nœud non feuille, la valeur de son sous-arbre gauche est plus petite qu'elle, et la valeur de son sous-arbre droit est supérieure à celle. Une étape supplémentaire qu'un arbre de recherche binaire est un arbre d'équilibre binaire. En plus d'assurer l'ordre, l'arbre d'équilibre binaire peut également maintenir la différence de hauteur entre les sous-arbres gauche et droit de chaque nœud et pas plus de 1. Les arbres équilibrés courants sont des arbres AVL, des triages, des arbres rouges et noirs, des arbres extensibles, etc.
Un arbre rouge et noir est un arbre de recherche binaire, mais ajoute un bit de stockage à chaque nœud pour représenter la couleur du nœud, qui peut être rouge ou noir. En limitant la façon dont chaque nœud ombrage sur n'importe quel chemin de la racine à la feuille, l'arbre-noir rouge garantit qu'aucun chemin ne sera deux fois plus long que les autres chemins, approchant ainsi l'équilibre.
L'arbre rouge et noir satisfait 5 propriétés:
Notez que dans un arbre rouge-noir, pointez l'enfant du nœud foliaire de l'arbre binaire traditionnel à nul et appelez nulle le nœud foliaire dans l'arbre-noir rouge. Le nœud NIL contient un pointeur vers le nœud parent, ce qui peut être la raison pour laquelle Null est nécessaire pour être changé en nulle.
1. Fonctionnement d'insertion
Tout d'abord, insérez le nouveau nœud pour insérer l'arborescence de recherche binaire (les nouveaux nœuds insérés sont tous au niveau des nœuds de feuilles) et les dessiner en rouge. Rerisez ensuite sa couleur ou faites-la pivoter pour maintenir les propriétés de l'arbre rouge et noir. L'ajustement est divisé en trois situations suivantes:
1 nouveau nœud n n'a pas de nœud parent (c'est-à-dire qu'il est situé sur la racine)
Peignez le nouveau nœud n comme noir.
2 Le nœud parent P du nouveau nœud n est noir
Pas besoin de s'ajuster.
3 Le nœud parent p du nouveau nœud n est rouge
Parce que l'arbre rouge et noir ne permet pas deux nœuds rouges consécutifs (propriété 4), il doit être ajusté. Selon la couleur du nœud oncle de n, il est divisé en deux situations: (nous prenons le nœud parent de N
3.1 Le nœud oncle U du nouveau nœud n est rouge. Le nœud parent P et le nœud uncle U du nouveau nœud N sont peints comme du noir, et le nœud de grand-père G est peint comme rouge, de manière à garantir que le nombre de nœuds noirs contenus sur le chemin de G à chaque nœud nul est cohérent avec celui d'origine. Mais comme nous transformons G en rouge, si le père de G est également rouge, cela peut conduire à deux nœuds rouges consécutifs (violant la nature 4), il est donc nécessaire de revérifier si G viole la nature de l'arbre rouge et noir.
3.2 Le nœud oncle U du nouveau nœud n est noir. Si le nouveau nœud N est l'enfant gauche de son nœud parent P: dessinez son nœud parent P en noir, dessinez son nœud grand-père G comme rouge, puis tournez G à droite une fois.
Si le nouveau nœud N est l'enfant droit de son nœud parent P: effectuez une rotation gauche sur son nœud parent, le problème sera transformé en la situation de l'enfant gauche.
2. Supprimer l'opération
La méthode de "Introduction aux algorithmes" et Wikipedia consiste à supprimer un nœud noir D, "Push Down" le noir de D vers son nœud enfant C, c'est-à-dire que C a une couche supplémentaire de noir en plus de sa propre couleur, puis continue de déplacer la couche de noir de noire arbre, de sorte que le nombre de nœuds noirs sur tous les chemins est réduit d'un seul et reste égal. Pendant le mouvement vers le haut, certaines couleurs de nœud peuvent devoir être tournées et modifiées pour garantir que le nombre de nœuds noirs sur le chemin reste inchangé.
Cette approche peut être bénéfique pour l'implémentation du code (qui peut être utilisée de manière itérative), mais il n'est pas pratique de comprendre (croire personnellement). Afin de comprendre la priorité, j'ai fait la classification suivante en fonction de la question de savoir si l'enfant du nœud supprimé D est nul:
1 Les deux enfants dont le nœud D a été supprimé est nul
1.1 Si le nœud supprimé D est rouge, remplacez simplement D par nil.
1.2 Le nœud supprimé D est noir (prenons D comme exemple)
1.2.1 Les deux enfants du nœud B, dont le frère D, ont été supprimés, sont nuls
Le nœud B du frère est peint comme le nœud rouge et le nœud parent P est peint comme noir.
À moitié rouge et à moitié noir sur la figure signifie que le nœud peut être rouge ou noir. Si P s'est avéré rouge, le nombre de nœuds noirs sur le chemin après modification est le même qu'avant la suppression D; Si P s'est avéré noir, la suppression D entraînera un nombre moins de nœuds noirs sur le chemin qu'avant la suppression, vous devez donc continuer à vérifier si le changement du nombre de nœuds noirs sur le chemin passant par P affecte les propriétés de l'arbre rouge et noir.
1.2.2 Le nœud Brother B du nœud D a un enfant non nulle
L'enfant doit être rouge, sinon le nombre de nœuds noirs sur le chemin du nœud parent de D à chaque nœud feuille variera (violation 5).
Si cet enfant est le bon enfant, dessinez le bon enfant de B comme noir, dessinez B comme couleur d'origine de son nœud parent P, dessinez P en noir, puis tournant P avec une gauche.
Si cet enfant est l'enfant gauche, dessinez l'enfant gauche de B comme noir, B comme rouge, puis tourne à droite B une fois, le problème sera transformé en la situation de l'enfant droit.
1.2.3 Les deux enfants du nœud B, qui ont été supprimés, ne sont pas nuls
Si B est rouge, les deux enfants de B doivent être noirs. Dessinez B en noir, l'enfant gauche de B comme rouge, puis effectuez une rotation gauche de P.
Si B est noir, les deux enfants de B doivent être rouges. Dessinez le nœud parent de B comme noir, l'enfant droit de B comme noir, la couleur d'origine de B comme son nœud parent P, puis tournent P avec une gauche.
2 Les deux enfants dont le nœud D a été supprimé ne sont pas nuls
Selon l'arborescence de recherche binaire pour supprimer les nœuds, trouvez le nœud successeur de D, échangez le contenu de D et S (la couleur reste inchangée), et le nœud supprimé devient S. si S possède un nœud qui n'est pas nulle, puis continue de remplacer S par le nœud successeur de S jusqu'à ce que les deux enfants du nœud supprimé soient nul. Le problème se transforme en situation où les deux enfants du nœud supprimé sont nul.
3 Le nœud supprimé D a un enfant non nulle
Cet enfant C doit être un nœud rouge, sinon le nombre de nœuds noirs sur le chemin de D à chaque nœud nul sera différent (violation 5).
Le contenu de D et C est échangé (la couleur reste la même), le nœud supprimé devient C, et le problème se transforme en situation où les deux enfants du nœud supprimé sont nuls.
Traversion des arbres binaires
Il existe trois types de traversées dans les arbres binaires: la traversée précommande, la traversée moyenne et la traversée post-ordre. Il existe deux types d'implémentations de traversée: la récursivité et l'itération. Dans cet article, nous discuterons de la façon d'utiliser un code plus élégant pour implémenter la traversée des arbres binaires.
Tout d'abord, je définirai un nœud d'un arbre binaire:
classe publique Treenode {int Val; Treenode à gauche; Treenode à droite; public Treenode (int x) {val = x; }}
1. Traversion précommande
En termes simples, la traversée de précommande consiste à accéder d'abord au nœud parent, puis à accéder à l'enfant gauche et enfin à accéder à l'enfant droit, c'est-à-dire pour traverser l'ordre du parent, de gauche et de droite.
L'implémentation récursive est très simple, le code est le suivant:
Solution de classe publique {list <Integer> result = new ArrayList <Neger> (); public list <Integer> preorgeTraversal (Treenode root) {dfs (root); Résultat de retour; } private void dfs (Treenode root) {if (root == null) {return; } result.add (root.val); dfs (root.left); dfs (root.Right); }} L'implémentation itérative nécessite une pile pour stocker le bon nœud qui n'est pas accessible. Le code est le suivant:
Solution de classe publique {public list <Integer> preorderTraversal (Treenode root) {list <Integer> result = new ArrayList <Integer> (); if (root == null) {return result; } Pile <serenode> pile = new Stack <seReNode> (); stack.push (root); while (! stack.isempty ()) {Treenode curr = stack.pop (); result.add (curr.val); if (curr.right! = null) {stack.push (curr.right); } if (curr.left! = null) {stack.push (curr.left); }} Retour Résultat; }}
2. Traversion inférieure
En termes simples, la traversée de l'ordre moyen consiste à accéder d'abord à l'enfant gauche, puis à accéder au nœud parent et enfin à accéder à l'enfant droit, c'est-à-dire une traversée dans l'ordre de gauche, de parent et de droite.
Le code récursif est également plus facile, comme indiqué ci-dessous:
Solution de classe publique {public list <Integer> inOrderTaversal (Treenode root) {list <Integer> result = new ArrayList <Integer> (); Recurse (racine, résultat); Résultat de retour; } private void recurse (Treenode root, list <Integer> result) {if (root == null) return; recurse (root.left, résultat); résultat.add (root.val); recurse (root.Right, résultat); }} La méthode d'écriture ci-dessus est différente du code récursif de traversée de précommande. Nous utilisons des variables membres pour stocker les résultats de la traversée dans la traversée de précommande, et ici, nous utilisons les paramètres de la méthode pour enregistrer les résultats de la traversée. Les deux méthodes d'écriture sont OK, utilisez ce que vous voulez.
La mise en œuvre itérative de la traversée de l'ordre intermédiaire n'est pas aussi simple que la traversée de précommande. Bien que cela nécessite également une pile, les conditions de terminaison itérative sont différentes. Imaginez que pour un arbre binaire, le nœud auquel nous accédons d'abord est son nœud le plus à gauche. Nous pouvons bien sûr atteindre son nœud le plus à gauche à travers une boucle de temps, mais lorsque nous nous replions, comment savons-nous si l'enfant de gauche d'un nœud a été accessible? Nous utilisons une variable Curr pour enregistrer le nœud actuellement consulté. Lorsque nous avons accédé au bon nœud d'un sous-arbre, nous devons retomber au nœud parent du sous-arbre. Pour le moment, Curr est nul, nous pouvons donc l'utiliser pour distinguer si le sous-arbre gauche d'un nœud a été accessible. Le code est le suivant:
Solution de classe publique {public list <Integer> inOrderTaversal (Treenode root) {list <Integer> result = new ArrayList <Integer> (); Stack <serenode> pile = new Stack <rerenode> (); Treenode curr = root; while (curr! = null ||! stack.isempty ()) {while (curr! = null) {stack.push (curr); curr = curr.left; } curr = stack.pop (); result.add (curr.val); curr = curr.Right; } Retour Résultat; }}
3. Traversion post-ordre
En termes simples, la traversée post-ordre consiste à accéder d'abord à l'enfant de gauche, à accéder à l'enfant droit et enfin à accéder au nœud parent, c'est-à-dire une traversée dans l'ordre de gauche, de droite et de parent.
En imitant la traversée de l'ordre moyen, vous pouvez facilement écrire une implémentation récursive de la traversée post-ordre:
Solution de classe publique {public List <Integer> PostOrderTraversal (Treenode Root) {List <Integer> result = new ArrayList <Integer> (); Recurse (racine, résultat); Résultat de retour; } private void recurse (Treenode root, list <Integer> result) {if (root == null) return; recurse (root.left, résultat); recurse (root.Right, résultat); résultat.add (root.val); }} L'itération de la traversée post-ordre nécessite également une identification pour distinguer si les enfants gauche et droit d'un nœud ont été accessibles. Sinon, les enfants gauche et droit seront accessibles à leur tour. S'il est accessible, le nœud sera accessible. À cette fin, nous utilisons une pré-variable pour représenter le nœud que nous avons visité. Si le nœud que nous avons visité est l'enfant gauche ou droit du nœud actuel, cela signifie que les enfants gauche et droit du nœud actuel ont été accessibles, puis nous pouvons accéder au nœud. Sinon, nous devons entrer les enfants gauche et droit pour y accéder à leur tour. Le code est le suivant:
Solution de classe publique {public List <Integer> PostOrderTraversal (Treenode Root) {List <Integer> result = new LinkedList <Integer> (); Stack <serenode> pile = new Stack <rerenode> (); if (root! = null) stack.push (root); Treenode pre = root; while (! stack.isempty ()) {Treenode curr = stack.Peek (); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val); stack.pop (); pre = curr; } else {if (curr.right! = null) stack.push (curr.right); if (curr.left! = null) stack.push (curr.left); }} Retour Résultat; }} Il existe une autre implémentation relativement simple de l'itération de la traversée post-ordre. Nous savons que l'ordre de la traversée de précommande est le parent, la gauche et la droite, tandis que l'ordre de la traversée post-ordre est gauche, à droite et parent. Donc, si nous modifions légèrement la traversée de précommande et la modifions dans l'ordre du parent, à droite et à gauche, alors c'est juste l'opposé de l'ordre de la traversée post-ordre. Après y accéder dans cet ordre, nous pouvons inverser le résultat d'accès à la fin. La mise en œuvre itérative de la traversée de précommande est relativement facile. Selon la méthode d'écriture ci-dessus, nous pouvons l'implémenter comme suit:
Solution de classe publique {public List <Integer> PostOrderTraversal (Treenode Root) {List <Integer> result = new LinkedList <Integer> (); Stack <serenode> pile = new Stack <rerenode> (); if (root! = null) stack.push (root); while (! stack.isempty ()) {Treenode curr = stack.pop (); result.add (curr.val); if (curr.left! = null) stack.push (curr.left); if (curr.right! = null) stack.push (curr.right); } Collection.Reverse (résultat); Résultat de retour; }}
4. Résumé
La mise en œuvre récursive des trois traversées est facile. Il est préférable d'écrire la mise en œuvre d'itération de la traversée de précommande, et une seule pile est nécessaire; La traversée de l'ordre intermédiaire est la plus difficile. En plus de déterminer si la pile est vide, la condition de boucle doit également déterminer si le nœud actuel est vide pour indiquer si le sous-arbre gauche a été traversé; Si l'itération de la traversée ultérieure est convertie en itération de traversée de précommande, c'est beaucoup plus facile. Sinon, il est également nécessaire d'enregistrer le nœud d'accès précédent pour indiquer si les sous-arbres gauche et droit du nœud actuel ont été accessibles.