Löschen in AVL - Bäumen
- Löschen eines Blattes bzw. eines Randknotens
( Knoten mit 1 Sohn )
- Höhenreduzierung ändert Balancierungsfaktoren der Vaterknoten
- ggf. fortgesetzte Rebalancierung erforderlich (nur möglich für Knoten mit BF = ? 2 auf dem Weg vom zu löschenden Element zur Wurzel).
- Löschen eines Knotens (Schlüssel x) mit 2 Söhnen kann auf
diese Fälle zurückgeführt werden.
- x wird ersetzt durch kleinsten Schlüssel y im rechten
Unterbaum von x (oder größten Schlüssel im linken
Unterbaum)
- führt zur Änderung des Balancierungsfaktors für v