Das Löschen eines Elements aus einem AVL-Baum ist dasselbe wie das Löschen aus einem BST, mit der Ausnahme, dass der Baum möglicherweise neu ausbalanciert werden muss. Wie im Abschnitt „Löschen von Elementen aus einem BST“ erläutert, sucht der Algorithmus zum Löschen eines Elements aus einem Binärbaum zunächst nach dem Knoten, der das Element enthält. Lassen Sie current auf den Knoten zeigen, der das Element im Binärbaum enthält, und parent auf den übergeordneten Knoten des Knotens current. Der aktuelle Knoten kann ein linker oder rechter untergeordneter Knoten des übergeordneten Knotens sein.
Beim Löschen eines Elements treten zwei Fälle auf.

Fall 1: Der aktuelle Knoten hat kein linkes untergeordnetes Element, wie in Abbildung unten (a) dargestellt. Um den aktuellen-Knoten zu löschen, verbinden Sie einfach den übergeordneten-Knoten mit dem rechten untergeordneten Knoten des aktuellen-Knotens, wie in Abbildung unten (b) gezeigt. Die Höhe der Knoten entlang des Pfads vom übergeordneten Knoten bis zum Wurzelknoten hat sich möglicherweise verringert. Um sicherzustellen, dass der Baum ausgeglichen ist, rufen Sie

balancePath(parent.element);

Fall 2: Der aktuelle Knoten hat ein linkes untergeordnetes Element. Lassen Sie rightMost auf den Knoten zeigen, der das größte Element im linken Teilbaum des Knotens current enthält, und parentOfRightMost auf den übergeordneten Knoten von rightMost -Knoten, wie in Abbildung unten (a) gezeigt. Der Knoten rightMost kann kein rechtes untergeordnetes Element haben, aber möglicherweise ein linkes untergeordnetes Element. Ersetzen Sie den Elementwert im Knoten current durch den im Knoten rightMost und verbinden Sie den Knoten parentOfRightMost mit dem linken untergeordneten Knoten des Knotens rightMost-Knoten und löschen Sie den Knoten rightMost, wie in Abbildung unten (b) dargestellt.

Die Höhe der Knoten entlang des Pfads von parentOfRightMost bis zur Wurzel hat sich möglicherweise verringert. Um sicherzustellen, dass der Baum ausgeglichen ist, rufen Sie

balancePath(parentOfRightMost);