Heim >Java >javaLernprogramm >Implementieren der Löschmethode

Implementieren der Löschmethode

WBOY
WBOYOriginal
2024-07-25 10:39:33646Durchsuche

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);

Implementing the delete Method

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.

Image description

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!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn