AVl-Baum: Warum und an was erkenne ich hier die Rotation?
-
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.
Nun hab ich aber das Problem, dass ich an bestimmten Stelle nicht verstehe warum.
Laut meiner Lösung muss an der Stelle eine Linksrotation um die 9 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 eines AVL-Baums zulässig!
Könnt ihr mir sagen an was ich erkenne, dass ich hier eine Linksrotation machen muss?
Das Bild davon findet ihr hier: http://s7.directupload.net/file/d/3130/mxz74as2_jpg.htm
-
bei avl muss der ganze baum balanziert sein, nicht nur die teilbaeume. zwischen der (5)-node und (13)-node ist der unterschied 2ebenen, wobei meiner erinnerung nach, die unbalance dann an der (6) node ist (links 1 rechts 3) und diese sollte rotiert werden, hmhmh.
-
Ich verstehe nicht ganz was du meinst.
Ich glaub aber eher das bei mir das Problem beim Erkennen der einzelnen Höhen liegt.
Wenn ich von der Node 6 ausgehe ist Blatt 3 und Blatt 13 auf Höhe 0. Richtig?
Wenn ich von Node 12 ausgehe ist Blatt 13 auf Höhe 0. Welche Höhe hat dann Node 9?
Welche Höhen haben eigentlich Nodes generell?
Die wichtigste Frage:
In meinen Folien steht, dass die Höhe eines Knotens die maximale Distanz nach unten zu den Blättern ist.
Heißt das also dass der Knoten 12 drei verschiedene Höhen hat? Und zwar je nachdem welchen Teilbaum man ansieht? Wenn ich den Teilbaum 12-13 ansehe hat der Knoten 12 die Höhe 1, richtig?
Wenn ich mir den Teilbaum 12-9-8 ansehe hat dann der Knoten 12 die Höhe 2. Wenn ich nun den Teilbaum 12-13 mit 12-9-8 vergleiche habe ich einen Unterschied von 1. Er ist also noch nicht entartet.
Wenn ich nun aber den Teilbaum 12-9-10-11 anschaue, hat der Knoten 12 eine Höhe 3. Dieser Teilbaum in Vergleich mit mit Teilbaum 12-13 ergibt mir einen Unterschied von 2 und ist somit entartet.
Bin ich mit meiner Schlussfolgerung noch richtig? Wie aber erkenne ich nun um welche Knoten ich wann drehen muss?
-
bandchef schrieb:
Ich verstehe nicht ganz was du meinst.
ich meine:
Ich glaub aber eher das bei mir das Problem beim Erkennen der einzelnen Höhen liegt.
Wenn ich von der Node 6 ausgehe ist Blatt 3 und Blatt 13 auf Höhe 0. Richtig?
ich weiss nicht auf welche zeichnung du dich beziehst. allerdings 'wenn ich von node 6 ausgehe' bedeutet quasi 'node 6 ist level 0'
Wenn ich von Node 12 ausgehe ist Blatt 13 auf Höhe 0. Welche Höhe hat dann Node 9?
dritte zeichnung? da gehst du immer noch von 6 aus, weil das die root/wurzel vom baum ist. bedenke, der ganze sinn von AVL ist einen balanzierten baum als ganzes zu haben, nicht nur balanzierte aeste, denn ansonsten konntest du immer sagen 'vom parent aus gesehen sind beide leafs immer balanziert', aber es geht ums ganze.
Welche Höhen haben eigentlich Nodes generell?
wenn man deine letzte zeichnung nimmt:
Level 0: 6
Level 1: 5 10
Level 2: 3 9 12
Level 3: 8 11 13
Level 4: 16Die wichtigste Frage:
In meinen Folien steht, dass die Höhe eines Knotens die maximale Distanz nach unten zu den Blättern ist.
Heißt das also dass der Knoten 12 drei verschiedene Höhen hat? Und zwar je nachdem welchen Teilbaum man ansieht? Wenn ich den Teilbaum 12-13 ansehe hat der Knoten 12 die Höhe 1, richtig?
wenn du das tun wuerdest, aber bei AVL machst du das nicht! und nein, jede node wird anhand der distanz zur root bewertet.
Wenn ich mir den Teilbaum 12-9-8 ansehe hat dann der Knoten 12 die Höhe 2. Wenn ich nun den Teilbaum 12-13 mit 12-9-8 vergleiche habe ich einen Unterschied von 1. Er ist also noch nicht entartet.
aber wenn du dir den ganzen baum anschaust, hat er doch schieflage.
Wenn ich nun aber den Teilbaum 12-9-10-11 anschaue, hat der Knoten 12 eine Höhe 3. Dieser Teilbaum in Vergleich mit mit Teilbaum 12-13 ergibt mir einen Unterschied von 2 und ist somit entartet.
Bin ich mit meiner Schlussfolgerung noch richtig? Wie aber erkenne ich nun um welche Knoten ich wann drehen muss?
drei einfache schritte.
1. berechne wie hoch jede node in relation zur wurzel ist
2. finde fuer jede node heraus was die level der am max entfernten child node ist
3. check fuer jede node ob linke und rechte childnode bei der max entfernung zur childnodes +-1 sind, ansonsten musst du so rotieren, dass es sich wieder ausgleicht. wenn also rechts +2 uebergewicht ist, rotierst du einmal nach links.
-
Danke jetzt hab ich das verstanden!
Wenn nun der zu löschende Schlüssel die Wurzel bzw. ein Knoten mit ZWEI Nachfolgern ist, verstehe ich NICHT wie ich hier dann löschen muss. Ich habe im Internet (meine Unterlagen geben leider dazu nix her) eine gute Beschreibung gefunden, die aber anscheinend auch nicht immer funktioniert:
- Für den Fall dass man ein Ersatzknoten suchen muss, nimmt man (je nach Balance des gelöschten Knotens) den linken oder rechten Unterbaum und sucht darin das am weitesten rechts bzw. das links liegende Element im Unterbaum.
Hier erst noch ein Bild von einem AVl-Baum in dem ich löschen möchte: http://s1.directupload.net/file/d/3135/e87bms52_jpg.htm
In diesem AVL-Baum möchte ich nun bspw. den Knoten 4 nach der Beschreibung von oben löschen. Da es ja anscheinend egal ist welchen Unterbaum man nimmt, wähle ich den rechten Unterbaum und suche dort das am weitesten links liegende Element. Da es in diesem Unterbaum kein wirkliches linkestes Element gibt, ist wohl der Wert 6 das linkeste Element. Ich ersetze nun die 4 mit der 6 und die 9 rückt ran.
Laut meiner Lösung soll aber die 4 mit der 3 ersetzt werden. Also kann es doch anscheinend doch nicht egal sein, welchen Unterbaum man nimmt, oder? Was ist nun richtig? Wie geht's richtig?