Rot- und Schwarzbaum
Rote und schwarze Bäume sind Bäume, die häufig in Datenstrukturen und Algorithmen erwähnt werden, aber nicht im Detail erklärt werden können. Es sind auch Bäume, die in technischen Interviews oft gefragt werden. Unabhängig davon, ob es sich um die Materialien in Büchern oder online handelt, sind sie normalerweise starrer und schwer zu verstehen. Kannst du rote und schwarze Bäume auf intuitivere Weise verstehen? In diesem Artikel werden die Einfügungs- und Löschvorgänge von roten und schwarzen Bäumen in grafischer Weise erläutert.
Das Erlernen der Baumstruktur ist ein fortschrittlicher Prozess. Die Bäume, mit denen wir normalerweise in Kontakt kommen, sind binäre Bäume. In einfachen Worten hat jeder Nicht-Blattknoten und nur zwei Kinder, die als linkes Kind und das rechte Kind bezeichnet werden. Es gibt einen speziellen Baumtyp in einem binären Baum, der als binärer Suchbaum bezeichnet wird. Ein binärer Suchbaum ist ein geordneter Baum. Für jeden Nicht-Blattknoten ist der Wert seines linken Unterbaums kleiner als er, und der Wert seines rechten Teilbaums ist größer als er. Ein weiterer Schritt als ein binärer Suchbaum ist ein binärer Ausgleichsbaum. Zusätzlich zur Sicherstellung der Reihenfolge kann der binäre Gleichgewichtsbaum auch den Höhenunterschied zwischen den linken und rechten Unterbäumen jedes Knotens und nicht mehr als 1. gängige ausgewogene Bäume behalten, sind AVL -Bäume, Tätigkeiten, rote und schwarze Bäume, Dehnungsbäume und so weiter.
Ein rot -schwarzer Baum ist ein binärer Suchbaum, fügt jedem Knoten jedoch ein Speicherbit hinzu, um die Farbe des Knotens darzustellen, der rot oder schwarz sein kann. Durch die Begrenzung, wie jeder Knoten auf einem Pfad von Wurzel zu Blatt beschattet, stellt der rotschwarze Baum sicher, dass kein Pfad doppelt so lang ist wie die anderen Pfade, wodurch sich das Gleichgewicht nähert.
Der rote und schwarze Baum erfüllt 5 Eigenschaften:
Beachten Sie, dass in einem rot-schwarzen Baum das Kind des Blattknotens des traditionellen binären Baums auf Null zeigen und den Blattknoten im rot-schwarzen Baum null nennen. Der Nullknoten enthält einen Zeiger auf den übergeordneten Knoten, was der Grund sein kann, warum Null in Null geändert werden muss.
1. Einlegen Sie den Betrieb
Fügen Sie zunächst den neuen Knoten in den Weg zum Einfügen des binären Suchbaums (die neuen Knoten befinden sich alle an den Blattknoten) und zeichnen Sie ihn rot. Dann seine Farbe neu zeichnen oder sie drehen, um die Eigenschaften des roten und schwarzen Baumes aufrechtzuerhalten. Die Einstellung ist in die folgenden drei Situationen unterteilt:
1 neuer Knoten N hat keinen übergeordneten Knoten (d. H. Er befindet sich auf der Wurzel)
Malen Sie den neuen Knoten N als schwarz.
2 Der übergeordnete Knoten P des neuen Knotens N ist schwarz
Keine Notwendigkeit, sich anzupassen.
3 Der übergeordnete Knoten P des neuen Knotens N ist rot
Da der rote und schwarze Baum nicht zwei aufeinanderfolgende rote Knoten (Eigenschaft 4) zulässt, muss er angepasst werden. Nach der Farbe des Onkelknotens von N ist er in zwei Situationen unterteilt: (Wir nehmen den übergeordneten Knoten P von N als Beispiel als Beispiel und P als das richtige Kind als ähnliche Situation, sodass ich es nicht im Detail erklären werde.
3.1 Der Onkelknoten U des neuen Knotens N ist rot. Der übergeordnete Knoten P und Onkel -Knoten U des neuen Knotens N werden als schwarz gemalt, und der Großvaterknoten G wird als rot gestrichen, um sicherzustellen, dass die Anzahl der auf dem Pfad von g zu jedem Nullknoten enthaltenen schwarzen Knoten mit dem ursprünglichen übereinstimmt. Da wir jedoch G in rot verwandeln, kann es zu zwei aufeinanderfolgenden roten Knoten führen, wenn Gs Vater auch rot ist (gegen die Natur 4). Daher ist es notwendig, erneut zu überprüfen, ob G gegen die Natur des roten und schwarzen Baumes verstößt.
3.2 Der Onkelknoten U des neuen Knotens N ist schwarz. Wenn der neue Knoten N das linke Kind seines übergeordneten Knotens P ist: Zeichnen Sie seinen übergeordneten Knoten P als schwarz, zeichnen Sie seinen Großvaterknoten G als rot und drehen Sie dann einmal G nach rechts.
Wenn der neue Knoten N das rechte Kind seines übergeordneten Knotens P ist: Führen Sie eine linke Rotation seines übergeordneten Knotens durch, das Problem wird in die Situation des linken Kindes umgewandelt.
2. Betrieb löschen
Die Methode in "Einführung in Algorithmen" und Wikipedia besteht darin, einen schwarzen Knoten D zu löschen, das Schwarze von D zu seinem Kinderknoten C zu "drücken". Die Anzahl der schwarzen Knoten auf allen Pfaden wird um eins reduziert und bleibt gleich. Während der Aufwärtsbewegung müssen einige Knotenfarben möglicherweise gedreht und geändert werden, um sicherzustellen, dass die Anzahl der schwarzen Knoten auf dem Pfad unverändert bleibt.
Dieser Ansatz kann für die Implementierung des Codes (der auf iterative Weise verwendet werden kann) von Vorteil sein, aber es ist nicht zweckmäßig zu verstehen (persönlich glauben). Um Priorität zu verstehen, habe ich die folgende Klassifizierung erstellt, basierend darauf, ob das Kind des gelöschten Knotens D NIL ist:
1 Beide Kinder, deren Knoten D gelöscht wurde
1.1 Wenn der gelöschte Knoten D rot ist, ersetzen Sie einfach D durch NIL.
1.2 Der gelöschte Knoten D ist schwarz (nimm d als Beispiel)
1.2.1 Beide Kinder des Knotens B, deren Bruder D gelöscht wurde, sind Null
Ds Bruderknoten B wird als rot gestrichen und der Elternknoten P als schwarz gemalt.
Halb rot und halb schwarz in der Figur bedeutet, dass der Knoten rot oder schwarz sein kann. Wenn sich P als rot herausstellte, ist die Anzahl der schwarzen Knoten auf dem Pfad nach der Modifikation gleich wie vor der Löschung D; Wenn sich P als schwarz herausstellte, führt das Löschen von D zu einer weniger Anzahl schwarzer Knoten auf dem Pfad als vor der Löschung. Sie müssen daher weiter überprüfen, ob die Änderung der Anzahl der schwarzen Knoten auf dem Weg, das durch P verläuft, die Eigenschaften des roten und schwarzen Baumes beeinflusst.
1.2.2 Der Bruderknoten B des Knotens D hat ein Kind nicht nil
Das Kind muss rot sein, andernfalls variiert die Anzahl der schwarzen Knoten auf dem Pfad von Ds übergeordnetem Knoten zu jedem Blattknoten (Verletzung 5).
Wenn dieses Kind das rechte Kind ist, zeichnen Sie das rechte Kind von B als schwarz, zeichnen Sie B als ursprüngliche Farbe seines übergeordneten Knotens P, zeichnen Sie P als schwarz und drehen Sie dann P mit einem links.
Wenn dieses Kind das linke Kind ist, zeichnen Sie das linke Kind von B als schwarz, b als rot und drehen Sie dann einmal B nach rechts, das Problem wird in die Situation des rechten Kindes umgewandelt.
1.2.3 Beide Kinder des Knotens B, die gelöscht wurden, sind nicht nil
Wenn B rot ist, müssen die beiden Kinder von B schwarz sein. Zeichnen Sie B als schwarz, bs linkskind als rot und führen Sie dann eine linke Rotation von P. durch.
Wenn B schwarz ist, müssen die beiden Kinder von B rot sein. Zeichnen Sie den übergeordneten Knoten P von B als schwarz, bs rechter Kind als schwarz, bs ursprüngliche Farbe als übergeordnete Knoten P, und drehen Sie dann P mit einem links.
2 Beide Kinder, deren Knoten D gelöscht wurde
Nach dem Binär -Suchbaum zum Löschen von Knoten finden Sie den Nachfolgerknoten S von D, tauschen Sie den Inhalt von D und S (die Farbe bleiben unverändert) aus, und der gelöschte Knoten wird zu S. Wenn s einen Knoten hat, der nicht Null ist, ersetzen Sie weiterhin S durch den Nachfolgerknoten von S, bis beide Kinder der gelösten Knoten Nil sind. Das Problem verwandelt sich in die Situation, in der beide Kinder des gelöschten Knotens d Null sind.
3 gelöschter Knoten D hat ein Kind nicht Null
Dieses Kind C muss ein roter Knoten sein, sonst ist die Anzahl der schwarzen Knoten auf dem Pfad von D zu jedem Nullknoten unterschiedlich (Verletzung 5).
Der Inhalt von D und C wird ausgetauscht (die Farbe bleibt gleich), der gelöschte Knoten wird zu C, und das Problem verwandelt sich in die Situation, in der beide Kinder des gelöschten Knotens D nil sind.
Durchqueren von Binärbäumen
Es gibt drei Arten von Traverals in binären Bäumen: Vorbestellungen, Middle -Traversal- und Postorder -Traversal. Es gibt zwei Arten von Traversal -Implementierungen: Rekursion und Iteration. In diesem Artikel werden wir diskutieren, wie Sie einen eleganteren Code verwenden, um die Durchführung von Binärbäumen zu implementieren.
Erstens werde ich einen Knoten eines binären Baums definieren:
öffentliche Klasse Treenode {int val; Treenode links; Treenode rechts; public treenode (int x) {val = x; }}
1. Vorbestellungen
Einfach ausgedrückt: Vorbestellung durchträgt zuerst auf den übergeordneten Knoten zuzugreifen, dann auf das linke Kind zuzugreifen und schließlich auf das rechte Kind zuzugreifen, dh in der Reihenfolge von Eltern, links und rechts.
Die rekursive Implementierung ist sehr einfach, der Code lautet wie folgt:
öffentliche Klasse -Lösung {List <Integer> result = new ArrayList <Ganzzahl> (); public list <NeGeger> vorOrderTraversal (Treenode root) {dfs (root); Rückgabeergebnis; } private void dfs (treenode root) {if (root == null) {return; } result.add (root.val); dfs (root.left); DFS (Wurzel); }} Die iterative Implementierung erfordert einen Stapel, um den richtigen Knoten zu speichern, auf den nicht zugegriffen wird. Der Code ist wie folgt:
öffentliche Klasse -Lösung {publiclist <GanzEger> vorOrderTraversal (Treenode root) {list <Integer> result = new ArrayList <Grainger> (); if (root == null) {return Ergebnis; } Stack <Treenode> stack = new Stack <Treenode> (); 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); }} Rückgabeergebnis; }}
2.
Einfach ausgedrückt, mit mittlerer Reihenfolge zugreifen Sie zuerst auf das linke Kind, dann auf den übergeordneten Knoten zu und greifen schließlich auf das rechte Kind zu, dh in der Reihenfolge von links, übergeordnet und rechts.
Der rekursive Code ist auch einfacher, wie unten gezeigt:
öffentliche Klasse Lösung {publiclist <Neger> InOrderTraversal (Treenode root) {list <Integer> result = new ArrayList <Grainger> (); Wiederholung (Wurzel, Ergebnis); Rückgabeergebnis; } private void recurse (Treenode root, list <GanzEger> Ergebnis) {if (root == null) return; Wiederholung (Root.Left, Ergebnis); result.add (root.val); Wiederholung (Wurzel. Right, Ergebnis); }} Die obige Schreibmethode unterscheidet sich von dem rekursiven Code des Vorbestellverlaufs. Wir verwenden Mitgliedervariablen, um die Ergebnisse von Traversal in der Vorbestellung zu speichern, und hier verwenden wir Methodenparameter, um die Ergebnisse von Traversal zu speichern. Beide Schreibmethoden sind in Ordnung, verwenden Sie alles, was Sie möchten.
Die iterative Implementierung von Mid-Order-Traversal ist nicht so einfach wie die Vorbestellung. Obwohl es auch einen Stapel erfordert, sind die Bedingungen für die iterative Beendigung unterschiedlich. Stellen Sie sich vor, wir greifen für einen binären Baum den Knoten zuerst auf den linken Knoten. Wir können natürlich einen Knoten links in einer Weile erreichen, aber wenn wir zurückfallen, woher wissen wir, ob auf das linke Kind eines Knotens zugegriffen wurde? Wir verwenden eine Curr -Variable, um den aktuell aufgerufenen Knoten aufzuzeichnen. Wenn wir auf den richtigen Knoten eines Unterbaums zugegriffen haben, sollten wir auf den übergeordneten Knoten des Subtree zurückgreifen. Zu diesem Zeitpunkt ist Curr null, sodass wir dies verwenden können, um zu unterscheiden, ob auf den linken Unterbaum eines Knotens zugegriffen wurde. Der Code ist wie folgt:
öffentliche Klasse Lösung {publiclist <Neger> InOrderTraverSal (Treenode root) {list <Integer> result = new ArrayList <Grainger> (); Stack <Treenode> Stack = New Stack <Treenode> (); Treenode Curr = root; while (curr! = null ||! stack.isempty ()) {while (curr! Curr = Curr.Left; } Curr = stack.pop (); result.add (Curr.val); Curr = Curr.Right; } Rückgabeergebnis; }}
3.
Einfach ausgedrückt, der Nach-Order-Traversal besteht darin, zuerst auf das linke Kind zuzugreifen, auf das rechte Kind zuzugreifen und schließlich auf den übergeordneten Knoten zuzugreifen, dh in der Reihenfolge von links, rechts und Eltern.
Durch die Nachahmung der Durchquerung der mittleren Ordnung können Sie leicht eine rekursive Implementierung des Nachitentraversals schreiben:
öffentliche Klasse -Lösung {publiclist <GanzEger> postOrderTraversal (Treenode root) {list <Integer> result = new ArrayList <Grainger> (); Wiederholung (Wurzel, Ergebnis); Rückgabeergebnis; } private void recurse (Treenode root, list <GanzEger> Ergebnis) {if (root == null) return; Wiederholung (Root.Left, Ergebnis); Wiederholung (Wurzel. Right, Ergebnis); result.add (root.val); }} Die Iteration der Nachbestellung erfordert auch eine Identifizierung, um zu unterscheiden, ob die linken und rechten Kinder eines Knotens zugegriffen wurden. Wenn nicht, werden die linken und rechten Kinder nacheinander zugreifen. Wenn es zugegriffen wurde, wird der Knoten zugegriffen. Zu diesem Zweck verwenden wir eine Vorvariable, um den von uns besuchten Knoten darzustellen. Wenn der von uns besuchte Knoten das linke oder rechte Kind des aktuellen Knotens ist, bedeutet dies, dass die linken und rechten Kinder des aktuellen Knotens zugegriffen wurden, und dann können wir auf den Knoten zugreifen. Andernfalls müssen wir die linken und rechten Kinder betreten, um darauf zuzugreifen. Der Code ist wie folgt:
öffentliche Klasse -Lösung {publiclist <GanzEger> postOrderTraversal (Treenode root) {list <Integer> result = new LinkedList <Ganzzahl> (); Stack <Treenode> Stack = New Stack <Treenode> (); 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 (); vor = Curr; } else {if (curr.right! = null) stack.push (curr.right); if (curr.left! = null) stack.push (Curr.Left); }} Rückgabeergebnis; }} Es gibt eine weitere relativ einfache Implementierung der Iteration des Nachauftrags. Wir wissen, dass die Reihenfolge der Vorbestellung über Eltern, links und rechts ist, während die Reihenfolge der Nachbestellung links, rechts und Eltern ist. Wenn wir also den Vorbestellungen leicht ändern und in die Reihenfolge des übergeordneten, rechts und links ändern, dann ist es genau das Gegenteil der Reihenfolge der Nachbestellung. Nachdem wir in dieser Reihenfolge darauf zugegriffen haben, können wir das Zugriffsergebnis am Ende umkehren. Die iterative Implementierung von Vorbestellungen ist relativ einfach. Nach der obigen Schreibmethode können wir sie wie folgt implementieren:
öffentliche Klasse -Lösung {publiclist <GanzEger> postOrderTraversal (Treenode root) {list <Integer> result = new LinkedList <Ganzzahl> (); Stack <Treenode> Stack = New Stack <Treenode> (); 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); } Collections.Reverse (Ergebnis); Rückgabeergebnis; }}
4. Zusammenfassung
Die rekursive Implementierung aller drei Traverals ist einfach. Es ist am besten, die Iteration -Implementierung von Vorbestellungen zu schreiben, und es wird nur ein Stapel benötigt. Mit mittlerer Ordnung ist der schwierigste Traversal. Zusätzlich zur Bestimmung, ob der Stapel leer ist, muss die Schleifenbedingung auch feststellen, ob der aktuelle Knoten leer ist, um anzuzeigen, ob das linke Subtree durchquert wurde. Wenn die Iteration der nachfolgenden Durchquerung in die Vorbestellung der Durchlauf -Iteration umgewandelt wird, ist dies viel einfacher. Andernfalls ist es auch erforderlich, den vorherigen Zugriffsknoten aufzuzeichnen, um anzuzeigen, ob die linken und rechten Unterbäume des aktuellen Knotens zugegriffen wurden.