Der erste Teil des Algorithmus ist wieder aequivalent zu dem Loeschen aus einem binaeren Suchbaum. Zuerst lokalisieren wir den zu loeschenden Knoten wieder mit Hilfe der binaeren Suche. Wir nennen den zu loeschenden Knoten z.
* Datum: 11.12.1999
* Diese Methode loescht ein Element. Die Methode ist public und muss
* zum Loeschen benutzt werden.
* @return true wenn der Schluessel erfolgreich geloescht wurde.
* @return false wenn der Schluessel nicht vorhanden ist.
***********************************************************************/
public boolean delete(int key) {
rbelement x,y,z;
z=root;
while (z!=NIL) { // Standard binaere Suche
if (key==z.searchkey)
break; // z ist das Element, das wir
// loeschen.
else
z=(key<z.searchkey)?z.left:z.right;
}
if (z==NIL) return false; // Den Schluessel gibt es nicht
// in unserem Baum.
if ((z.left==NIL) || (z.right==NIL)) {
y=z;
} else {
y=z.right;
while (y.left!=NIL) y=y.left; // Nachfolger von z
}
Hat z keine zwei NIL-Unterbaeume, so lokalisieren wir das zu z naechst groessere Element in dem Rot-Schwarz Suchbaum. Dieses befindet sich im rechten Unterbaum von z, aufgrund der binaeren Suchbedingung. Es handelt sich jedoch um das kleinste Element in dem rechten Unterbaum von z. Der Nachfolger y von z hat einen leeren linken Unterbaum, da es sonst aufgrund der binaeren Suchbedingung einen Knoten mit einem Suchschluessel kleiner als der von y und groesser als der von z gaebe. Das waere ein Widerspruch zu der Forderung, dass y den zu z naechst groesseren Suchschluessel in dem Baum besitzt.
Das Ziel ist, den zu loeschenden Knoten durch seinen Nachfolger zu ersetzen. Damit waere die binaere Suchbedingung gewahrt und der Baum waere wieder ein Bianerbaum.
An dieser Stelle des Algorithmus enthaelt y eine Referenz auf einen Knoten mit mindestens einem leeren Unterbaum. Dieser Knoten ist ausserdem entweder z oder der Nachfolger von z.
x=y.left;
else
x=y.right;
if (y.parent!=null)
if (y==y.parent.left)
y.parent.left=x;
else
y.parent.right=x;
else
root=x;
if (y!=z)
z.searchkey=y.searchkey;
Das Loeschen von Elementen kann die definierenden Eigenschaften eines Rot-Schwarz Baumes verletzen. Betrachten wir vorerst die moeglichen Faelle, die bei dem Loeschen auftreten koennen. Es gibt symmetrische Faelle, die hier nicht gezeigt sind.
Das Minus-Zeichen im Fall c) deutet an, dass wir bei diesem Loeschvorgang einen schwarzen Knoten zuwenig haben. In den Faellen a) und b) wird keine der vier Rot-Schwarz Baum Eigenschaften verletzt.
Im Fall b) muss eine Farbe geaendert werden. Falls y ``rot'' ist, sind wir an diesem Punkt bereits fertig mit Loeschen, da wir einen roten Knoten stets loeschen koennen, und die Rot-Schwarz Baum Eigenschaften dennoch erhalten bleiben. Falls y schwarz ist, muessen wir wieder den Rot-Schwarz Baum ausgleichen, weil damit auf einem Pfad ein schwarzer Knoten zu wenig vorhanden ist.
Der Knoten x sei ein schwarzer Knoten in einem Rot-Schwarz Suchbaum T, und x sei der einzige Knoten, der die definierenden Eigenschaften eines Rot-Schwarz Baums verletzt. Abgesehen von x ist T ein Rot-Schwarz Baum.
Ist x das linke Kind seines Vorgaengerknoten, so bezeichnen wir das rechte Kind des Vorgaengerknotens als ``Schwester'' von x. Ist x das rechte Kind seines Vorgaengerknoten, so bezeichnen wir das linke Kind des Vorgaengerknotens als ``Schwester'' von x.
Fall 1: x ist die Wurzel. T ist ein Rot-Schwarz Baum
Fall 2: x ist nicht die Wurzel, und seine Schwester u ist rot. Sei y der Elternknoten von x und u. Diesen Fall transformieren wir in den Fall 3 oder 4.
u.color=BLACK;
x.parent.color=RED;
rotateLeft(x.parent);
u=x.parent.right;
}
Fall 2a)
b) x ist das rechte Kind von y: Rotiere y nach rechts, faerbe u schwarz und y rot. Wiederhole den Algorithmus.
Fall 3: x ist nicht die Wurzel, seine Schwester u ist schwarz und x ist das linke Kind seines Elternknoten y. z sei das linke und v das rechte Kind von u.
Fall 3.1: v und z sind schwarz.
u.color=RED;
x=x.parent;
}
Fall 3.1.2: y ist rot. Wir faerben u rot und y schwarz. T ist ein Rot-Schwarz Baum.
Fall 3.2: v ist schwarz und z ist rot. Indem wir z schwarz faerben und u rot, anschliessend u nach rechts rotieren, wandeln wir den Fall 3.2 in den Fall 3.3 um. Hier der Quellcode zu dem Fall 3.2:
u.left.color=BLACK;
u.color=RED;
rotateRight(u);
u=x.parent.right;
}
Fall 3.3: v ist rot. Wir muessen u nach links rotieren, v schwarz faerben, die Farbe von u gleich der Farbe von y setzen und y schwarz faerben. Dann ist T ein Rot-Schwarz Baum. Der Quellcode dazu:
x.parent.color=BLACK;
u.right.color=BLACK;
rotateLeft(x.parent);
|
Fall 4: x sei das rechte Kind von y. Dieser Fall ist symmetrisch zu dem Fall 3.
Aehnlich wie bei dem Einfuegen wurden auch damit alle moeglichen Faelle behandelt. Hier der gesamte Algorithmus zum Ausgleichen des Baumes nach dem Loeschen:
while ((x!=root) && (x.color==BLACK)) {
if (x==x.parent.left) {
rbelement u=x.parent.right;
if (u.color==RED) {
u.color=BLACK;
x.parent.color=RED;
rotateLeft(x.parent);
u=x.parent.right;
}
if ((u.left.color==BLACK) && (u.right.color==BLACK)) {
u.color=RED;
x=x.parent;
} else {
if (u.right.color==BLACK) {
u.left.color=BLACK;
u.color=RED;
rotateRight(u);
u=x.parent.right;
}
u.color=x.parent.color;
x.parent.color=BLACK;
u.right.color=BLACK;
rotateLeft(x.parent);
x=root;
}
} else {
rbelement u=x.parent.left;
if (u.color==RED) {
u.color=BLACK;
x.parent.color=RED;
rotateRight(x.parent);
u=x.parent.left;
}
if ((u.right.color==BLACK) && (u.left.color==BLACK)) {
u.color=RED;
x=x.parent;
} else {
if (u.left.color==BLACK) {
u.right.color=BLACK;
u.color=RED;
rotateLeft(u);
u=x.parent.left;
}
u.color=x.parent.color;
x.parent.color=BLACK;
u.left.color=BLACK;
rotateRight(x.parent);
x=root;
}
}
}
x.color=BLACK;
} // End of function deleteFixup
Das Ziel der while-Schleife ist, das doppelte ``Schwarz'' in dem Baum nach oben zu bewegen, bis die Variable x entweder eine Referenz auf einen roten Knoten enthaelt, den wir dann in der letzten Zeile der Methode schwarz faerben, x eine Referenz auf die Wurzel des Baumes enthaelt, in welchem Fall wir das doppelte Schwarz einfach entfernen koennen, oder passende Umformung durchgefuehrt werden koennen. Innerhalb der while-Schleife enthaelt x eine Referenz auf einen schwarzen Knoten, der das ``doppelte'' Schwarz besitzt. Da der Knoten x ``doppelt'' schwarz ist, kann der Knoten w (die Schwester von x) nicht NIL sein.
Die Kernidee hinter dem Algorithmus ist, dass in jedem Fall die Anzahl der schwarzen Knoten von und einschliesslich der Wurzel des gezeigten Teilbaumes zu jedem Unterbaum 1 bis 5 gleich bleibt. Dabei wird das doppelte ``Schwarz'' des Knoten x beruecksichtigt.
Im Fall 3.1 und dem symmetrischen Fall sind x, die Schwester von x sowie beide Kinder der Schwester schwarz. Es wird ein ``Schwarz'' von x und dessen Schwester weggenommen, und dem Elternknoten der beiden eins hinzugefuegt. War der Elternknoten rot, so sind wir an der Stelle fertig, ansonsten enthaelt der Elternknoten von x das doppelte Schwarz und der Algorithmus wird mit diesem Knoten wiederholt.
Im Fall 3.3 (welcher 3.2 einschliesst) und dem symmetrischen Fall wird der Baum rotiert und der Algorithmus terminiert anschliessend.
Es stellt sich nun die Frage, in welcher Zeit die Operation Einfuegen laeuft.
Zum Auffinden des zu loeschenden Elementes benutzen wir die bianere Suche, die
in einem Rot-Schwarz Baum mit n Elementen 
Zeit benoetigt. In
den Faellen 2, 3.2 und 3.3 sowie den symmetrischen Faellen terminiert der Algorithmus
nach einer konstanten Anzahl von Farbvertauschungen und hoechstens 3 Rotationen.
Im Fall 3.1 wird das doppelte Schwarz mit jedem Schleifendurchlauf um einen
Knoten nach oben in Richtung Wurzel des Baumes verschoben. Da die Hoehe des
Baumes eine natuerliche Zahl ist, verringert sich das Problem mit jedem Schleifendurchlauf
um ``1''. Der Fall 3.1 laeuft demnach in einer Zeit von 
und damit
Damit ist die gesamte Komplexitaet des Einfuegens .
Am Ende der Loeschen-Methode muessen wir noch sicherstellen, dass die Wurzel schwarz ist, damit unsere Vereinfachung im Einfuegen-Algorithmus weiterhin moeglich und gueltig ist.
