AVL-Baum die Rotationen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Hi Leute!
Ich soll in einen AVl-Baum der Reihe nach diese Werte einfügen:5,6,9,12,13,4,8,10,11,16,15,146,4,2,1. |
Hi Leute!
Ich hab nun aber das Problem, dass ich bestimmte Stellen nicht verstehe warum das so gemacht wird.
Erstmal das Bild. Das Bild davon findet ihr hier: ![[a]](/images/paperclip.gif "Dateianhänge") AVL-Baum
Laut meiner Lösung muss an der Stelle eine Doppelrotation bzw. als nächster Schritt erst eine Linksrotation um die 9 angewendet werden und dann eine Rechtsrotation angewendet werden. Ich erkenne aber nicht warum gerade hier eine Linksrotation nötig wird! Die höhe der Teilbäume die an der 9 hängen unterscheiden sich beide nur um 1; und das ist laut Definition der Höhen eines AVL-Baums zulässig!
Könnt ihr mir sagen an was ich erkenne, dass ich hier eine Linksrotation machen muss? Die nachfolgende Rechtsrotation ist klar, denn die Höhe des rechten Teilbaumes von der 12 ausgehend ist 1; die Höhe des linken Teilbaumes von der 12 ausgehend 3. Die Formel darauf angewendet die oben rechts steht, sagt dann das 2 [mm] \leq [/mm] 1 sein soll, was nicht stimmt und somit der Teilbaum von der 12 ausgehen nicht ausbalanciert ist. Das Problem ist also wirklich die Linksrotation!
Könnt ihr mir helfen?
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Fr 11.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[a]](uploads/forum/00941439/forum-i00941439-n001.JPG "Dateianhänge"){kind=small}
AVL-Baum