Das Entfernen von Knoten aus einem rot-schwarzen Baum ist keine leichte Aufgabe, daher ist es sinnvoll, ihn in mehrere Teile aufzuteilen und jeden Fall separat zu betrachten.
cartoonbank.ru
Im letzten Artikel haben wir die Regeln für die Bildung eines rot-schwarzen Suchbaums untersucht und die Fälle des Ausgleichs beim Hinzufügen von Elementen berücksichtigt.
Lassen Sie uns nun über das Löschen von Elementen sprechen.
Nehmen Sie zum Beispiel diesen rot-schwarzen Baum:
Denken Sie daran, dass die Haupteigenschaft eines rot-schwarzen Baums links und rechts von jedem Knoten dieselbe schwarze Höhe hat. Daher geben wir in den Abbildungen neben jedem Knoten den Wert der schwarzen Höhe an, damit wir in jeder Phase ihre Stabilität überprüfen können.
Teile und herrsche
Das Entfernen eines Elements aus einem rot-schwarzen Baum ist keine so einfache Aufgabe, wie es auf den ersten Blick erscheinen mag. Ich schlage daher vor, es in mehrere Teile zu unterteilen und jedes einzeln zu betrachten.
Teilen wir die Aufgabe zunächst in zwei Kategorien ein:
- Farbe des entfernten Knotens: K oder H.
- Anzahl der untergeordneten Knoten: 2, 1 oder 0
Als Ergebnis erhalten wir eine Matrix mit 6 Optionen: K2, Ch2, K1, Ch1, K0, Ch0.
Für jede Option wird der entsprechende Knoten unseres Baums angezeigt.
Betrachten wir den Entfernungsprozess für jede Option.
K2 - roter Knoten mit zwei Kindern
Die Aufgabe, einen Knoten mit zwei untergeordneten Knoten zu entfernen, reduziert sich auf die Aufgabe, einen Knoten mit einem oder null untergeordneten Knoten zu entfernen.
Dazu müssen Sie das nächstgelegene Element finden, das kleiner oder größer als das gelöschte ist, und diese austauschen.
Beachten Sie, dass Sie beim Austauschen von Elementen nur die Werte in den Knoten ändern und die Farbe beibehalten müssen, um die Baumstruktur nicht zu beschädigen und die Schwarzhöhe nicht zu ändern.
Nach dem Austausch müssen Sie den Artikel von seinem neuen Speicherort entfernen Es ist entweder das Element ganz rechts im linken Zweig (maximal links) oder das Element ganz links im rechten Zweig (minimal rechts). In jedem Fall hat es kein Kind links oder rechts. Somit wird die Aufgabe des Entfernens eines Knotens mit 2 untergeordneten Elementen auf die Aufgabe des Entfernens eines Elements mit 1 oder 0 untergeordneten Elementen reduziert:
- K2 => K1 oder K0
Ch2 - schwarzer Knoten mit zwei Kindern
Ähnlich wie im vorherigen Fall geben wir ein Beispiel für das Löschen des schwarzen Knotens 16.
Wie Sie sehen, wird die Aufgabe nach dem Austausch auf das Löschen eines Elements mit einem untergeordneten Element reduziert:
- Ch2 => Ch1 oder Ch0
K1 - roter Knoten mit einem Kind
Wenn der rote Knoten kein untergeordnetes Element hat, hat er stattdessen ein schwarzes NIL-Element und die schwarze Höhe des roten Knotens ist 1. Daher muss die schwarze Höhe andererseits auch 1 sein. Da der rote Knoten jedoch kein rotes untergeordnetes Element haben kann Farben, dann sollte sein anderes Kind schwarz sein. Da die schwarze Höhe 1 sein muss, kann es sich nur um ein schwarzes NIL-Element handeln, da bei einem normalen schwarzen Element die Höhe höher ist.
Somit findet kein K1-Fall statt.
Ch1 - schwarzer Knoten mit einem Kind
Wenn das schwarze Element kein untergeordnetes Element hat, gibt es stattdessen ein schwarzes NIL-Element mit einer schwarzen Höhe 1. Daher sollte auf der anderen Seite ein roter Knoten ohne untergeordnete Elemente vorhanden sein. Um ein solches Element zu entfernen, reicht es aus, den Wert des roten Elements auf den schwarzen Knoten zu übertragen, während die schwarze Höhe erhalten bleibt.
K0 - roter Knoten ohne Kinder
Der einfachste Fall. Wir entfernen einfach das Element und ersetzen es durch eine NIL-Referenz: Durch
Entfernen des roten Elements wird die schwarze Höhe nicht geändert.
CH0 - schwarzer Knoten ohne Kinder
Das Entfernen eines schwarzen Knotens ohne untergeordnete Elemente ist ebenfalls sehr einfach: Wir ersetzen ihn durch einen Verweis auf NIL.
Glaubst du, das ist fast alles? Haha, sechsmal.
Nach dem Entfernen des schwarzen Elements ändert sich die schwarze Höhe des Teilbaums und Sie müssen ihn für das übergeordnete Element ausgleichen.
Das gelöschte Element in den Figuren wird mit x bezeichnet, seiner Höhe - h. Wenn wir gerade mit dem Balancieren beginnen, ist h = 1, aber es kann mit rekursiven Aufrufen zunehmen.
Stellen wir zur Bestimmtheit fest, dass das gelöschte Element das richtige Kind war. Nach dem Entfernen nahm seine Höhe ab und wurde h. Dies bedeutet, dass die Größe des linken Sohnes h + 1 bleibt. Wir müssen die Höhen der linken und rechten Teilbäume ausrichten und sie gleich h + 1 machen.
Ich schlage vor, die Aufgabe erneut in mehrere Teile zu unterteilen. Welche Möglichkeiten haben wir?
Der Elternteil kann rot oder schwarz sein. Der linke Sohn kann auch schwarz oder rot sein. Und der richtige Sohn ist immer schwarz - von dort kamen wir nach dem Entfernen zum Balancieren.
Es sind 6 verschiedene Fälle zu berücksichtigen:
- KCH1 und KCH2 - der Elternteil ist rot, das linke Kind ist schwarz.
- CHK3 und CHK4 - der Elternteil ist schwarz, das linke Kind ist rot.
- HH5 und HH6 - der Elternteil ist schwarz, das linke Kind ist schwarz.
Wir werden uns mit Geduld und Popcorn eindecken, die interessantesten und mysteriösesten liegen vor uns.
1 - Eltern rot, linkes Kind schwarz mit schwarzen Enkelkindern
Solange wir die roten Knoten haben, können wir sie verschieben und / oder neu einfärben, um das Gleichgewicht der schwarzen Höhe wiederherzustellen. In diesem Fall können wir die rote Farbe vom Elternteil zum linken Sohn senken und so die schwarze Höhe des Elternteils ausrichten:
Stellen Sie anhand der Abbildung sicher, dass die schwarzen Höhen der Knoten a und b erhalten bleiben und die Höhe des gesamten Teilbaums gleich und gleich h + 1 geworden ist.
KCH2 - Elternteil ist rot, das linke Kind ist schwarz mit dem linken roten Enkel.
In diesem Fall reicht ein Neulackieren allein nicht aus. Wir müssen eine kleine Kurve nach rechts zwischen den Knoten 3-7 machen. Infolgedessen können wir die Höhe des rechten Teilbaums auf h + 1 erhöhen: Ein
grüner Knoten bedeutet, dass er entweder schwarz oder rot sein kann.
Hinweis. Wenn der Knoten "1" schwarz und "c" rot ist, kann das Problem auf die Variante HH5 reduziert werden.
CHK3 - der Elternteil ist schwarz, der linke Sohn ist rot, der rechte Enkel hat schwarze Urenkel
Wenn Sie schwarze Urenkel haben, können Sie das Enkelrot neu streichen und es an den rechten Teilbaum senden, indem Sie eine kleine Rechtskurve von 3 bis 7 machen. Fragen Sie nicht warum, vertrauen Sie einfach und überprüfen Sie, ob sich die schwarze Höhe stabilisiert hat:
Beachten Sie, dass der rote Knoten 5 das Schwarz nicht erhöht Höhe.
CHK4 - der Elternteil ist schwarz, der linke Sohn ist rot, der rechte Enkel hat einen roten Urenkel
Weiter im roten Wald gibt es mehr schwarze Brennhölzer und weniger rote, nämlich durch Umfärben der roten Knoten ist es möglich, die schwarze Höhe zu stabilisieren.
In diesem Fall müssen Sie eine große Linkskurve machen, die aus zwei kleinen Kurven 5-3 und 5-7 besteht. Knoten b hat seine Farbe von rot nach schwarz geändert und damit seine Höhe um 1 erhöht. Stellen Sie sicher, dass sich die schwarze Höhe stabilisiert hat.
HCH5 - der Elternteil ist schwarz, der linke Sohn ist schwarz mit dem rechten roten Enkel.
Immer weniger rote Elemente in unserem Teilbaum streichen den letzten roten Enkel schwarz neu und machen eine große Linkskurve, wie im vorherigen Fall.
Überprüfen Sie, ob sich die schwarze Höhe des Teilbaums stabilisiert hat.
HCH6 - der Elternteil ist schwarz, der linke Sohn ist schwarz, seine Enkel sind ebenfalls schwarz
Und dann kam der Moment, als das rote Holz ausgegangen war. Es gibt nichts zu tun, Sie müssen den schwarzen Knoten rot malen und damit die schwarze Höhe von Knoten 7 ausgleichen, aber nicht durch Erhöhen der schwarzen Höhe des rechten Teilbaums, sondern durch Verringern der schwarzen Höhe des linken Teilbaums. Infolgedessen nimmt die schwarze Höhe unserer gesamten Struktur um 1 ab, und wir müssen die Vorfahren rekursiv als Ausgleich bezeichnen.
Löschbeispiel mit Ausgleich und Rekursion
Wir haben uns alle 6 Fälle von Schwarzhöhenausgleich angesehen, nachdem wir ein Element aus dem rot-schwarzen Baum entfernt hatten. Um ein besseres Gefühl dafür zu bekommen, wie dies alles funktioniert, entfernen wir weiterhin Knoten 30 aus dem ursprünglichen Baum.
Der erste Schritt besteht einfach darin, Knoten 30 zu löschen. Der
zweite Schritt besteht darin, das Balancieren auf seinem übergeordneten Knoten 25 zu starten.
Es gibt einen Fall von HH6:
Die Höhe von Knoten 25 wurde mit Trauer in zwei Hälften stabilisiert.
Der dritte Schritt ist das Balancieren auf der Ebene des Großvaters - für Knoten 20.
Um es lustiger und klarer zu machen Zeichnen wir den ganzen Baum vor und nach dem Balancieren. Dies ist bei HK4 der Fall:
Beachten Sie, wie sich der rot-schwarze Baum nach dem Balancieren geändert hat, einige der Elemente aus dem linken Teilbaum nach rechts verschoben wurden, die Höhe stabilisiert wurde, das Element entfernt wurde, alle sind glücklich!
Das Entfernen von Elementen aus einem rot-schwarzen Baum ist eine der schwierigsten Vorgänge bei der Arbeit mit binären Suchbäumen. Im Kurs " Algorithmen und Datenstrukturen " betrachten wir nicht nur binäre Suchbäume, sondern auch viele andere interessante Algorithmen. Weitere Details finden Sie im Kursprogramm.
