AVL-Baum - Testen ob einer vorliegt

[andi677]

Hey an alle!

Ich muss eine Methode implementieren, die bei gegebenen Binärbaum testet, ob ein AVL Baum vorliegt.
Die Musterlösung gibt folgendes vor:

public boolean isAVLTree(Knoten root){
if (root==null){
return true;
}
return
Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 &&
isAVLTree(root.left) &&
isAVLTree(root.right);

// getHeight() gibt einem die Höhe zurück

Nun die Frage: Irgendwie kann ich nicht nachvollziehen, warum man zusätzlich zum rekursiven Aufruf noch die Differenz beim return ermittelt... Wär echt nett, wenn mir jemand das return hier entschlüsseln könnte.

Vielen vielen Dank!

 

[Gast2]

Soweit ich mich erinnern kann muss ein AVL Baum ausbalanciert sein. Das heißt der linke Teilbaum muss genauso hoch wie der rechte Teilbaum sein. Allerdings würde ich dann prüfen ob die Differenz 0 ist, und nicht <= 1. Aber vielleicht passt meine Definition auch nicht ganz.

 

[hüteüberhüte]

Ja, das ist richtig. Für jeden Knoten muss geprüft werden, ob die Höhe der Teilbäume sich max. um 1 unterscheidet. arrow: Dann ist er balanciert.) Also ist rekursives Vorgehen angebracht

 

[andi677]

danke, jetzt hats klick gemacht ;-)

 

[hüteüberhüte]

Aber nicht nur AVL-Bäume sind höhenbalanciert, außerdem lassen sich Bäume auch noch in Arrays/Feldern speichern, je nach dem, wie die Darstellung ist.

War vorhin am überlegen, ob es nicht reichen würde, nur die unteren beiden Ebenen des Baums zu betrachten. Aber vermutlich nicht. welche Aufgaben habt ihr noch so in diesen Zusammenhang?