Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Kann mir Jemand erklären wieso das kein AVL-Baum ist?
Hey, kann mir Jemand erklären wieso das kein AVL-Baum ist und was geändert werden müsste, damit es ein AVL-Baum wird?
Bild im Anhang, danke!
Attachment:
Bildschirmfoto 2020-02-23 um 15.46.31.png: https://fsi.cs.fau.de/unb-attachments/post_163547/Bildschirmfoto 2020-02-23 um 15.46.31.png
Bei einem AVL-Baum darf der Betrag der Höhe der Wurzel <=1 sein.
Die Höhe eines Knoten berechnet sich aus der Höhe des linken Teilbaums minus der Höhe des rechten Teilbaums, wobei bei einem nicht vorhandenen Teilbaum stattdessen -1 eingesetzt wird.
Somit ergibt sich für ein Blattknoten also immer die Höhe 0.
Wenn du nun rekursiv von unten nach oben die Höhe berechnest, welche Höhe hat die Wurzel?
Die Höheneigenschaft stimmt bei deinem Beispiel, der Baum verletzt die binäre Suchbaum eigenschaft: der linke Teilnahm von Knoten 3 muss zum linken Teilnahm von 6 werden → dadurch ist dann der Balancefaktor falsch und der Baum muss rebalanciert werden .
1 „Gefällt mir“
Nein, die Höheneigenschaft passt nicht.
Aber ja, die binäre Sucheigenschaft passt auch nicht.