[AuD] RS-Bäume: Einfügen und Löschen

Einfügen von Knoten z: rot machen
(einmal ein paar Variablen definieren: Vater von z: x, Bruder von x: y und Vater von x: v)
Fall 1: y auch rot: x, y, v umfärben -> Fälle mit z := v durchspielen
Fall 2: y ist schwarz und z rechtes Kind von x: Link-Rotation um x -> weiter mit Fall 3
Fall 3: y ist schwarz, z ist linkes Kind von x: x, v umfärben, Rechts-Rotation um v -> fertig

Das ist jetzt alles für den Fall, dass x das linke Kind von v ist.
Wenn x das rechte Kind von v ist, dann ist alles spiegelverkehrt: linkes Kind ist rechtes Kind ist (und umgekehrt) und Links-Rotation ist Rechts-Rotation (und umgekehrt).

====================================================================================================

Löschen von Knoten z:
(Erinnerung: wenn z zwei nicht leere direkte Kinder besitzt, dann wird der Wert von z ersetzt durch den größten Wert des linken Unterbaums und dieser Knoten wird dann gelöscht - wenn der linke Unterbaum leer ist, wird der kleinste Wert des rechten Unterbaums genommen)
Also ist z ein Knoten mit einem null-Knoten als direktes Kind:
z ist rot -> fertig
z ist schwarz -> fixen (für die RS-Eigentschaft der gleichen Anzahl schwarzer Knoten auf jedem Pfad)
(Variablendefinitionen: x und x' sind direkte Kinder von z; x' ist leer, also wird z durch x ersetzt) im Folgenden ist x bereits an die Stelle von z gewandert:
- z war Wurzel => x ist schwarz -> fertig; => x ist rot -> umfärben -> fertig
- x ist rot -> umfärben -> fertig
- x ist schwarz (im Folgenden: y ist Bruder von x (also Bruder vom ehemaligen z) und v ist Vater von x und y - Achtung: x ist an der Stelle von z, also ist y nicht x' !)
-- Fall 1: y ist rot: v, y umfärben, Links-Rotation um v, y auf den neuen Bruder von x setzen => weiter mit Fall 2-4 (je nachdem was anfällt)
-- Fall 2: y und beide Kinder von y sind schwarz: y rot machen (sprich umfärben) -> weiter mit x = v
-- Fall 3: y ist schwarz, rechtes Kind von y ist schwarz und linkes Kind von y ist rot: y und linkes Kind von y umfärben, Rechts-Rotation um y -> weiter mit x und neuem y (Fall 4)
-- Fall 4: y ist schwarz und rechtes Kind ist rot: y bekommt die Farbe von v, dann werden v und rechtes Kind von y schwarz gemacht, Links-Rotation um v -> falls y nach der Rotation die Wurzel ist, schwarz färben

Das ist jetzt alles für den Fall, dass x das linke Kind von v ist.
Wenn x das rechte Kind von v ist, dann ist alles spiegelverkehrt: linkes Kind ist rechtes Kind ist (und umgekehrt) und Links-Rotation ist Rechts-Rotation (und umgekehrt).