Algorithmus zum Löschen von Schlüssel s

1. [1.] Lösche den Schlüssel wie in einem gewöhnlichen binären Suchbaum.
   Dabei wird ein Knoten explizit entfernt: entweder der zu löschende Knoten oder aber das 'Minimum im rechten Teilbaum'.
   Es sei k dieser explizit entfernte Knoten.
2. [2.] Falls k nicht die Wurzel ist: Aktualisiere den Balance-Index für den Vater v des Knotens k.
   
   • Ist b(v) =1, so bist du fertig, denn dann hat sich die Höhe des bei v beginnenden Teilbaumes nicht geändert.
   • Ist b(v) = 0, so setze k = v und beginne erneut bei 2.
   • Ist b(v) =2, so überprüfe anhand des folgenden Schaubildes, welche Maßnahme getroffen werden muss.