Hallo,
die Aufgabe hat zwar nicht direkt mit Java zu tun aber vl. kann mir doch jemand weiterhelfen. Ich soll zuerst einen AVL-Baum erstellen indem ich die folgenden Werte der Reihenfolge nach einsortiere. 5,6,9,12,13,3,8,10,11,16,15,14,7,4,2,1 - das funktioniert auch soweit. Auf folgender Seite kann man das visuell darstellen https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Nun sollen die Werte 12,8,5,4,3,6,15,14 der Reihe nach gelöscht werden. Das kann ebenfalls mit diesem Tool dargestellt werden. Wir haben als Def. aufgeschrieben: Hat ein Knoten zwei Nachfolger, so geht man von diesem Knoten in den rechten Teilbaum und sucht dort den Wert der am weitesten links steht und ersetzt den zu löschenden Knoten mit diesem(der im rechten TeilBaum am weitesten links steht)
So nun das Problem. Wenn ich aus dem oben erstellten Baum die 8 löschen will, müsste ich doch laut Def. von der 8 in den rechten Teilbaum gehen. Dort ist nur noch die 9, also ersetze ich die 8 durch die 9. Das Tool geht aber in den linken Teilbaum und nimmt die 7.wieso?
Vielen Dank
die Aufgabe hat zwar nicht direkt mit Java zu tun aber vl. kann mir doch jemand weiterhelfen. Ich soll zuerst einen AVL-Baum erstellen indem ich die folgenden Werte der Reihenfolge nach einsortiere. 5,6,9,12,13,3,8,10,11,16,15,14,7,4,2,1 - das funktioniert auch soweit. Auf folgender Seite kann man das visuell darstellen https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Nun sollen die Werte 12,8,5,4,3,6,15,14 der Reihe nach gelöscht werden. Das kann ebenfalls mit diesem Tool dargestellt werden. Wir haben als Def. aufgeschrieben: Hat ein Knoten zwei Nachfolger, so geht man von diesem Knoten in den rechten Teilbaum und sucht dort den Wert der am weitesten links steht und ersetzt den zu löschenden Knoten mit diesem(der im rechten TeilBaum am weitesten links steht)
So nun das Problem. Wenn ich aus dem oben erstellten Baum die 8 löschen will, müsste ich doch laut Def. von der 8 in den rechten Teilbaum gehen. Dort ist nur noch die 9, also ersetze ich die 8 durch die 9. Das Tool geht aber in den linken Teilbaum und nimmt die 7.wieso?
Vielen Dank
Zuletzt bearbeitet: