Wähle einen Schlüssel zum Löschen. Beobachte zuerst die Suche
und das Entfernen des Knotens. Falls dabei ein schwarzer Knoten
verschwindet, werden anschließend die Rot-Schwarz-Eigenschaften
durch Umfärbungen und Rotationen wiederhergestellt.
Danach kannst du die Löschung Schritt für Schritt durchlaufen.
Baumansicht
Eine orange Umrandung markiert beteiligte Knoten.
„DB“ bezeichnet einen vorübergehend doppelt schwarzen
Knoten beziehungsweise ein doppelt schwarzes NIL-Blatt.
Wichtiger Unterschied zum Einfügen:
Beim Löschen muss unter Umständen ein schwarzer Knoten ersetzt werden.
Die dadurch fehlende schwarze Höhe wird in der Korrektur als
zusätzliche Schwärze bei x betrachtet.
Ein doppelt schwarzes NIL-Blatt ist ein didaktisches Hilfssymbol;
es ist kein dauerhaft gespeicherter zusätzlicher Baumknoten.
Komplexität: Suche und Löschen benötigen
O(log n) Zeit.