Implementieren der Löschmethode

Das Löschen eines Elements aus einem AVL-Baum ist dasselbe wie das Löschen aus einem BST, außer 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 current-Knotens. Der aktuelle-Knoten kann ein linkes oder rechtes Kind 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

auf

balancePath(parent.element);

Fall 2: Der aktuelle Knoten hat ein linkes Kind. Lassen Sie rightMost auf den Knoten zeigen, der das größte Element im linken Teilbaum des aktuellen-Knotens enthält, und parentOfRightMost auf den übergeordneten Knoten von rightMost Knoten, wie in Abbildung unten (a) gezeigt. Der rightMost-Knoten 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) gezeigt.

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

auf

balancePath(parentOfRightMost);

Das obige ist der detaillierte Inhalt vonImplementieren der Löschmethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!