AVL-Baum Rotation

[Tommy23]

hi. ich versuche gerade mit python einen avl baum zu programmieren, aber meine rotationen funktionieren nicht :/
Weiß jemand was ich falsch mache?
Freue mich über eine Antwort!
LG

Code: Alles auswählen

def rechtsRotation(self, knoten):
        neu=knoten.holeLinks()
        alt_links=neu.holeRechts()
        alt=knoten
        knoten=neu
        alt.setzeLinks(alt_links)
        neu.setzeRechts(alt)

[miracle173]

Hallo
Versuche deinen Algorithmus zu simulieren.
Ich nehme an, jeder Knoten deiner Struktur hat einen linken und rechten Nachbar (double linked list, doppelt verkettete Liste),
den du auslesen (holeLinks,holeRechts)
oder setzen(setzeLinks, setzeRechts) kannst.
Nehmen wir an du hast zwei Knoten 1 und 2 und 2 ist der rechte Nachbar von 1.
l1 verweist auf den linken, r1 auf den rechten Nacbar von 1, l2 und r2 sind analog definiert.
Die Werte von l1 und l2 sind irrlevant.
Versuche nun den Algorithmus zu simulieren.

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

rechtsRotation(self, knoten=2)

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

neu         ?
alt_links   ?
knoten      2 <==
alt         ?

neu=knoten.holeLinks()

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

neu         1 <==
alt_links   ?
knoten      2
alt         ?

alt_links=neu.holeRechts()

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

neu         1
alt_links   2 <==
knoten      2
alt         ?

alt=knoten

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

neu         1
alt_links   2
knoten      2
alt         2 <==

knoten=neu

Code: Alles auswählen

l1          ?
r1          2
l2          1
r2          ?

neu         1
alt_links   2
knoten      1 <==
alt         2

alt.setzeLinks(alt_links)

Code: Alles auswählen

l1          ?
r1          2
l2          2 <==
r2          ?

neu         1
alt_links   2
knoten      1 
alt         2

neu.setzeRechts(alt)

Code: Alles auswählen

l1          ?
r1          2 <== 
l2          2
r2          ?

neu         1
alt_links   2
knoten      1 
alt         2

Ist das das gewünschte Ergebnis? Ich denke nicht.


Du kannst auch folgende Überlegungen durchführen.

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. alt_links=neu.holeRechts()
3. alt=knoten
4. knoten=neu
5. alt.setzeLinks(alt_links)
6. neu.setzeRechts(alt)

Anmerkung: knoten wird nach 4. nicht mehr verwendet. Der Schritt4. kann also entfallen.

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. alt_links=neu.holeRechts()
3. alt=knoten
4. 
5. alt.setzeLinks(alt_links)
6. neu.setzeRechts(alt)

Anmerkung:
1. neu=knoten.holeLinks()
2. alt_links=neu.holeRechts()=(knoten.holeLinks()).holeRechts()=knoten
also
2. alt_links=knoten
das ergibt:

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. alt_links=knoten
3. alt=knoten
4. 
5. alt.setzeLinks(alt_links)
6. neu.setzeRechts(alt)

Anmerkung:
Wegen alt_links=knoten und alt=knoten kann 5 und 6 vereinfacht werden zu:
5. knoten.setzeLinks(knoten)
6. neu.setzeRechts(knoten)

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. alt_links=knoten
3. alt=knoten
4. 
5. knoten.setzeLinks(knoten)
6. neu.setzeRechts(knoten)

Anmerkung: alt_links und alt werden nicht mehr benötigt.

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. 
3. 
4. 
5. knoten.setzeLinks(knoten)
6. neu.setzeRechts(knoten)

Anmerkung: Der Wert von knoten wird nicht verändert, deshalb kann die Reihenfolge von 5. und 6. vertauscht werden.

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. 
3. 
4. 
5. neu.setzeRechts(knoten)
6. knoten.setzeLinks(knoten)

(knoten.holeLinks()).setzeRechts(knoten).setzeRechts(knoten)=(knoten.holeLinks()).setzeRechts(knoten)

Code: Alles auswählen

1. neu=knoten.holeLinks()
2. 
3. 
4. 
5. (knoten.holeLinks()).setzeRechts(knoten)
6. knoten.setzeLinks(knoten)

Anmerkung: neu wird nicht mehr verwendet

Code: Alles auswählen

1. 
2. 
3. 
4. 
5. (knoten.holeLinks()).setzeRechts(knoten)
6. knoten.setzeLinks(knoten)

Anmerkung: (knoten.holeLinks()).holeRechts()=knoten, also ist (knoten.holeLinks()).setzeRechts(knoten) überflüssig.

Code: Alles auswählen

1. 
2. 
3. 
4. 
5. 
6. knoten.setzeLinks(knoten)

Wiederum die Frage: Ist das das was du tun willst?

[miracle173]

hi. ich versuche gerade mit python einen avl baum zu programmieren, aber meine rotationen funktionieren nicht :/
Weiß jemand was ich falsch mache?
(...)

Auf Wikipedia finde ich vier Arten der Rotation. Welche hast du hier implementiert?