Transcript
Bei der Untersuchung des Löschvorgangs aus einem Rot-Schwarz-Baum betrachten wir zunächst den Löschvorgang selbst, d.h. das Entfernen eines Blattes. Das betroffene Knotenmuster ist
mit den Bezeichnungen E=zu löschender Knoten, V=Vaterknoten, B=Bruderknoten und K=Kindknoten. Einfach zu behandeln ist ein roter zu löschender Knoten.
Der Bruderknoten kann fehlen, ist aber, wenn vorhanden, ebenfalls Rot. Wird E nun gelöscht, so ändert sich nichts an der Schwarztiefe, und der Löschvorgang ist abgeschlossen. Ebenfalls einfach zu behandeln ist ein schwarzer zu löschender Knoten mit einem roten Kind.
K wird schwarz eingefärbt und nimmt die Stelle von E ein, womit sich an der Schwarztiefe dieses Zweiges nichts verändert hat (der rechte Baumteil ist per Voraussetzung korrekt). Besitzt E kein Kind, hängt das weitere Vorgehen von B und V ab. Betrachten wir zunächst den konfliktfrei lösbare Falle, dass B ein rotes Kind besitzt
Nach Entfernen von E übernimmt K die Rolle von V und V wird linkes Kind von K, das dabei schwarz gefärbt wird. Die Schwarztiefe bleibt so erhalten. Ohne Umfärbung von K lässt sich so auch der Fall eines roten V lösen. Auch noch unkritisch ist der Fall, dass B keine Kinder besitzt und V rot ist. Nach Entfernen von E tauschen V und B die Farbe, was insgesamt die Schwarztiefe konstant lässt.
Besitzt B zwei rote Kinder,
so kann V an die Position E rücken und das linke Kind die Rolle von V übernehmen:
Auch hier hat sich offenbar nichts geändert. Der letzte noch zu untersuchende problemlose Basisfall betrifft die gleiche Ausgangslage, jedoch nun mit
zwei roten Kindern von B
Nach dem folgende Tausch ist zunächst wieder alles in Ordnung
Der einzige wirklich kritische Fall sind schwarze E, V und B sowie fehlende Kinder:
Nach Entfernen von E bleibt nur, die Farbe von B zu wechseln:
Der Teilbaum ist zwar nun wieder korrekt, jedoch hat die Schwarztiefe insgesamt abgenommen, so dass oberhalb von V weitergemacht werden muss.
Untersuchen wir nun hier die auftretenden Möglichkeiten allgemein. Falls V, B, und beide Kinder von B schwarz sind,
genügt es, B rot einzufärben. Damit ist auch der rechte Teilbaum nun in der Schwarztiefe reduziert, und die Untersuchung kann rekursiv mit V fortgesetzt werden. Ist V rot (und der Rest identisch), genügt ein Farbwechsel zwischen V und B
Im rechten Teilbaum bleibt dabei die Farbtiefe erhalten, im linken steigt sie wieder um die zuvor verlorene Einheit, so dass der Baum ausgeglichen ist. Besitzt B zwei rote Kinder
so kann man durch Umfärben von B und K den Baum in diesen Fall überführen:
Damit hat sich zwar noch nichts geändert, aber wir können nun durch Rotieren einen Zustand erreichen, den wir schon behandelt haben:
An der Rolle von E ändert sich nichts, aber er hat nun einen roten Vater und einen schwarzen Bruder, wovon wir oben bereits einen Fall erfolgreich behandelt haben. Auch bei verschiedenfarbigen Kindern von B ist eine Rotation möglich:
Die Rolle von V ist dabei nebensächlich, das rote Kind wird schwarz gefärbt
Man überzeugt sich leicht, dass der Baum hierdurch sogar repariert ist.
Bleibt als ausstehender Fall noch der folgende:
Zyklisch tauschen wir
Auch hierdurch wird der Baum repariert.
