Ich versuche derzeit, die Implementierung von Rot-Schwarz-Bäumen zu verstehen, wie sie von Okasaki gegeben wurde, und Lösche Methoden von Kahrs (die nicht typisierte Version ).
In der Lösch-Implementierung wird eine Funktion app verwendet, die die untergeordneten Knoten des gelöschten Knotens zu "verschmelzen" scheint. Und wieder scheint der Algorithmus die rot-rote Eigenschaft anstatt der schwarzen Höhe zu verwenden (bitte korrigiere mich, wenn ich falsch liege). Wir erzeugen immer rote Knoten (auch wenn wir die rot-rote Eigenschaft brechen) ). Gehe den Teilbaum entlang, der am gelöschten Knoten verwurzelt ist, korrigiere die rot-roten Verletzungen, sobald wir die Blätter erreicht haben, beginnen wir den Pfad hochzufahren (beginnend mit dem "neuen Baum" Merge), der die rot-rote Verletzung auf dem Pfad fixiert .
bh-1 und bh Teilbäume an einem Knoten auf dem Pfad erzeugen. Alle Hinweise auf eine Erklärung für diese "Zusammenführungs" -Operation wären großartig.
Bitte beachten Sie, das ist kein Hausaufgabenproblem oder irgendetwas anderes. Ich studiere unabhängig die in Okasaki gegebenen Implementierungen und fülle die "unordentlichen" Löschungen auch aus.
Danke.
Da zu diesem Thema viel gesagt werden kann, werde ich versuchen, so nah wie möglich bei Ihren Fragen zu bleiben, aber lassen Sie es mich wissen, wenn ich etwas Wichtiges verpasse.
app ? Sie haben Recht, dass app die rote Invariante statt der schwarzen auf dem Weg nach unten durchbricht und dies auf dem Weg nach oben behebt.
It app beendet oder führt zwei Teilbäume zusammen, die der Reihenfolge-Eigenschaft, schwarzen Invarianten, roten Invarianten folgen und die gleiche Schwarztiefe in einen neuen Baum haben, der auch der Ordnungseigenschaft, schwarzen Invarianten, gehorcht. und rote Invariante. Die einzige bemerkenswerte Ausnahme ist, dass der root oder app rb1 rb2 manchmal rot ist und zwei rote Unterbäume hat. Solche Bäume werden als "Infrarot" bezeichnet. Dies wird in delete behandelt, indem einfach die Wurzel in dieser Zeile auf schwarz gesetzt wird.
Anspruch 1 (Bestelleigenschaft) , wenn die Eingaben rb1 und rb2 die Eigenschaft order individuell (linker Teilbaum & lt; Knotenwert & lt; rechter Teilbaum) und den maximalen Wert in% co_de befolgen % ist kleiner als der minimale Wert in rb1 , dann entspricht rb2 ebenfalls der Eigenschaft order.
Dieser ist leicht zu beweisen. Tatsächlich kann man es sogar sehen, wenn man sich den Code anschaut - das app rb1 rb2 s bleibt immer links von a s oder b s, die immer links von b' s bleiben oder c s, die immer links von c' s bleiben. Und auch die d s und b' s gehorchen dieser Eigenschaft, da sie das Ergebnis von rekursiven Aufrufen von c' mit den Unterbäumen app und b sind, die den Anspruch erfüllen.
Anspruch 2 (rote Invariante) Wenn die Eingaben c und rb1 der roten Invariante gehorchen (wenn ein Knoten rot ist, dann sind beide seiner untergeordneten Objekte schwarz), dann gilt dies auch für alle anderen Knoten in rb2 , außer möglicherweise der Wurzel. Die Wurzel kann jedoch nur "Infrarot" sein, wenn eines ihrer Argumente eine rote Wurzel hat.
Beweis Der Beweis erfolgt durch Verzweigen der Muster.
app rb1 rb2 und app E x = x ist der Anspruch trivial app x E = x sagt die Anspruchshypothese, dass alle app (T R a x b) (T R c y d) , a , b und c schwarz sind. Daraus folgt, dass d der roten Invariante vollständig gehorcht (es ist nicht Infrarot).
app b c mit app b c übereinstimmt, müssen die Unterbäume T R b' z c' und b' schwarz sein (und der roten Invariante gehorchen), so dass c' der roten Invariante mit einer Infrarot-Wurzel gehorcht. T R (T R a x b') z (T R c' y d) einen schwarzen Knoten app b c erzeugt, so dass bc der roten Invariante gehorcht. Für T R a x (T R bc y d) interessiert es nur, dass app (T B a x b) (T B c y d) selbst die rot-invariante
app b c ein roter Knoten ist, kann es infrarot sein, aber die Unterbäume app b c und b' müssen dagegen die rote Invariante vollständig befolgen. Das heißt c' gehorcht auch der roten Invariante. Wenn nun T R (T B a x b') z (T B c' y d) schwarz wird, rufen wir bc auf. Das Schöne dabei ist, dass wir bereits wissen, welche zwei Fälle von balleft a x (T B bc y d) ausgelöst werden können: abhängig davon, ob balleft rot oder schwarz ist
Im ersten Fall passiert es, dass wir die Farbe des linken Teilbaums von Rot zu Schwarz vertauschen (und dabei niemals die Rot-Invariante brechen) und alles in einen roten Teilbaum setzen. Dann sieht a tatsächlich wie balleft a x (T B bc y d) aus, und das gehorcht der roten Invariante.
Andernfalls wird der Aufruf von T R (T B .. ..) (T B bc y d) zu balleft und der gesamte Punkt von balance a x (T R bc y d) dazu, dass rote Verletzungen auf Root-Ebene behoben werden.
Für balance wissen wir, dass app a (T R b x c) und a schwarz sein müssen, also ist b nicht infrarot, also entspricht app a b der roten Invariante. Dasselbe gilt für T R (app a b) x c , aber mit den Buchstaben app a (T R b x c) , a und b permutiert.
Anspruch 3 (schwarze Invariante) wenn die Eingaben c und rb1 der schwarzen Invariante gehorchen (jeder Pfad von der Wurzel zu den Blättern hat die gleiche Anzahl an schwarzen Knoten auf dem Weg) und haben die gleiche Schwarztiefe, rb2 gehorcht ebenfalls der schwarzen Invariante und hat die gleiche Schwarztiefe.
Beweis Der Beweis erfolgt durch Verzweigen der Muster.
app rb1 rb2 und app E x = x ist der Anspruch trivial app x E = x wissen wir, dass, da app (T R a x b) (T R c y d) und T R a x b die gleiche Schwarztiefe haben, auch ihre Unterbäume T R c y d , a , b und c . Durch die Behauptung (denken Sie daran, das ist Induktion!)% Co_de% wird auch der schwarzen Invariante gehorchen und die gleiche schwarze Tiefe haben. Jetzt verzweigen wir unseren Beweis auf d
app b c mit case app b c of ... übereinstimmt, ist es rot und seine Unterbäume app b c und T R b' z c' haben dieselbe Schwarztiefe wie b' (selbst), die wiederum die gleiche Schwarztiefe wie c' hat. und app b c , also a gehorcht der schwarzen Invariante und hat die gleiche Schwarztiefe wie seine Eingaben. d einen schwarzen Knoten T R (T R a x b') z (T R c' y d) erzeugt, aber wieder hat dieser Knoten die gleiche Schwarztiefe wie app b c und bc , also gehorcht a als Ganzes immer noch der schwarzen Invariante und hat die gleiche schwarze Tiefe als seine Eingänge.d wissen wir sofort wieder, dass die Unterbäume T R a x (T R bc y d) , app (T B a x b) (T B c y d) , a und b alle die gleiche Schwarztiefe haben wie c . Wie zuvor, verzweigen wir unseren Beweis auf d
app b c ein roter Knoten der Form case app b c of ... ist, erhalten wir wieder, dass app b c , T R b' z c' , b' und c' dieselbe Schwarztiefe haben, also auch a hat dieselbe schwarze Tiefe d schwarz wird, wenden wir die gleiche Argumentation wie in unserem vorherigen Anspruch an, um herauszufinden, dass die Ausgabe T R (T B a x b') z (T B c' y d) tatsächlich auch die Form hat
bc wobei balleft a x (T B bc y d) nur T R (T B .. ..) (T B bc y d) ist, die als schwarz eingefärbt sind, so dass der Gesamtbaum die schwarze Invariante erfüllt und eine Schwarztiefe mehr als% (T B .. ..) , a , a oder% co_de aufweist %, also die gleiche Schwarztiefe wie die Eingaben b und c . d und T B a x b behält die schwarze Invariante bei. T B c y d) oder balance a x (T R bc y d) wissen wir, dass balance , app a (T R b x c) und app (T R a x b) c alle dieselbe Schwarztiefe haben und folglich a und b dasselbe Schwarz haben -depth, was bedeutet, dass c und app a b ebenfalls die gleiche Schwarztiefe haben Mein Schläger ist ein bisschen rostig, deshalb habe ich keine großartige Antwort darauf. Im Allgemeinen macht app b c das Löschen schnell, indem Sie alles in zwei Schritten ausführen können: Sie gehen zur Zielseite hinunter, dann fahren Sie weiter nach unten, um die Teilbäume zusammenzuführen, dann kommen Sie wieder und fixieren die Invarianten, während Sie gehen Weg zur Wurzel.
In dem Papier , auf das Sie verweisen, rufen Sie T R (app a b) x c (sobald Sie sich auf der Zielseite befinden) Ich denke, das ist der Hauptunterschied - die Rotationen sehen sonst ziemlich ähnlich aus), der sich rekursiv selbst auffindet, um das Element im Teilbaum zu finden, das Sie in den Zielort plumpsen können, und den Zustand des Teilbaums, nachdem dieses Element entfernt wurde. Ich glaube, dass der letzte Teil die Leistung dieser Implementierung beeinträchtigt.
Tags und Links haskell red-black-tree