Hilfe bei Algorithmen

[Mobalasch]

Hallo erstmal! Ich hoffe ihr könnt mir weiterhelfen!

Ich brauche hilfe bei einem beispiel und brings leider alleine nicht zusammen!

also ich habe einen avl baum der nicht ausbalanciert ist. ein pointer zeigt auf den knoten der wert -2 ist (was nicht sein darf)...

und die frage ist schreibe einen pseudocode der nur für diesen fall das problem behebt.

und vlt. könnt ihr mir noch bitte sagen was tupel sind das gehört zwar zur datenmodellierung aber ich hoffe ihr könnt mir bei den beiden sachen weiterhelfen!

ich möchte mich jetzt schon für alle antworten und hilfen bedanken!

[Sigi]

Du willst öh was mit deinem Baum machen? Da isn Knoten mit -2 drin den du rauslöschen willst?

Wiki oder google und du erfährst, was ne Tupel ist und zwar ne blöde Bezeichnung für Datensatz.

[Klotzkopp]

Du willst öh was mit deinem Baum machen?

Ausbalancieren.

Da isn Knoten mit -2 drin den du rauslöschen willst?

Nein, er hat einen Knoten mit einem Balancewert von -2. Das bedeutet, dass die Höhe des linken Teilbaums um 2 größer ist als die des rechten. Damit ist der Baum nicht ausbalanciert.

Wiki oder Google, und du erfährst, was ein AVL-Baum ist.

@Mobalasch:

In der Wikipedia ist das eigentlich recht gut beschrieben.

[Mobalasch]

das mit der balance ist mir schon klar und ich nehm an das hier eine rechtsrotation angewendet wird.

das problem ist einen code zu schreiben der speziell auf dieses beispiel bezogen das problem löst!

[Klotzkopp]

das mit der balance ist mir schon klar und ich nehm an das hier eine rechtsrotation angewendet wird.

Ob eine einfache Rotation ausreicht, hängt davon ab, wie der linke Teilbaum ausbalanciert ist.

[Mobalasch]

ich hab auch nur die informationen die ich schon geschrieben hab! Ich hab keinen aufgezeichneten baum! aber reichts nicht wenn du weißt das die balance -2 ist?

ich würd sagen das eine einfache rotation genügt!

und das mit dem code bekomm ich gar nicht hin!

[Klotzkopp]

ich hab auch nur die informationen die ich schon geschrieben hab! Ich hab keinen aufgezeichneten baum! aber reichts nicht wenn du weißt das die balance -2 ist?

Wer immer die Aufgabe gestellt hat, ist wohl der Meinung, dass du nicht mehr Informationen brauchst.

ich würd sagen das eine einfache rotation genügt!

Nicht zwangsläufig. Ein Beispiel:

    A

   / \

  B   C

 / \

D   E

   /

  F[/code]


A hat -2. Wenn du jetzt eine einfache Rotation machst, ...

[CODE]    B

   / \

  D   A

     / \

    E   C

   /

  F     

...hast du nichts gewonnen, denn jetzt hat B den Wert +2.

und das mit dem code bekomm ich gar nicht hin!

Wo liegt denn konkret das Problem? Kannst du denn eine einfach Rotation - egal in welche Richtung - als Pseudocode formulieren?

[Mobalasch]

also wenn ich deinen baum richtig gedeutet hab und in einmal nach rechts rotiere hab ich in B eine Balance von 0 und damit das problem behoben...

A

/ \

B C

/ \

D E

/

F

Und nach der rotation

B

/ \

D A

/ / \

F E C

[Klotzkopp]

Was für eine Rotation soll das denn sein? Wenn ich die Struktur richtig deute, hast du die Reihenfolge von DBFEAC auf FDBEAC geändert. Das ist nicht Sinn der Sache.

[Mobalasch]

Naja, eigentlich hab ich die struktur von ABCDEF auf BDAFEC geändert, aber das versickern kann ich ja nicht durchführen weil ich ja keine werte für die einzelnen Knoten habe...

[Klotzkopp]

Äh, solche Bäume liest man nicht zeilenweise. Das ist nicht eindeutig. Man beginnt beim Knoten ganz links und liest dann Linker Teilbaum - Elternknoten - Rechter Teilbaum. Bei jedem Teilbaum fängt man wieder ganz links an.

In meinen Beispiel kommt dabei vor und nach der Rotation dasselbe raus: DBFEAC. Nach deiner "Rotation" sieht es so aus, als ob F der linke Kindknoten von D wird. Das ändert die Reihenfolge.

[Mobalasch]

aber wenn vor und nach der rotation das selbe rauskommt hat sich nix verändert was dazu führt das auch das problem weiter besteht!

[Klotzkopp]

aber wenn vor und nach der rotation das selbe rauskommt

Was meinst du mit "rauskommt"?

hat sich nix verändert was dazu führt das auch das problem weiter besteht!

Nein. Du musst die Ordnung getrennt von der Struktur betrachten.

Ein AVL-Baum ist eine Datenstruktur, die ihre Elemente sortiert. Der linke Kindknoten ist immer "kleiner", der rechte "größer" als der Elternknoten.

Es gibt bei mehreren Elementen mehrere Möglichkeiten, diese Relation in einem Baum auszudrücken. Aber nur wenn die Balancewerte möglichst klein sind, ist eine optimale Suchgeschwindigkeit gewährleistet.

Die Rotationen im AVL-Baum ändern nicht die Reihenfolge der Elemente im Bezug auf die Ordnungsrelation. Sie ändern nur die Balance. Die Reihenfolge darf sich nicht ändern, sonst geht die Sortierung des Baums verloren. Deswegen ist deine Umformung unzulässig.

Die Struktur muss man natürlich so ändern, dass die Balancewerte wieder zwischen -1 und 1 liegen. Und da zeigt dir mein Beispiel, dass eine einfache Rotation nicht ausreicht. Du brauchst die bei Wikipedia beschriebene Doppelrotation, wenn bei einem Balancewert von -2 der Wert des linken Kindknotens positiv ist - eben wie in meinem Beispiel.

[Mobalasch]

wenn ich so rotiere wie ich das gemacht habe, steht noch immer im linken teilbaum das was kleiner ist und im rechten das was größer ist... aber trotzdem hat sich die reihenfolge verändert, und das muss sie auch, weil sonst eine rotation ja zu keinem ergebnis führen würde... die avl baum bedingungen bleiben mir durch die rotation erhalten aber die auftrittsreihenfolge ändert sich und das ist auch erlaubt!

[Klotzkopp]

wenn ich so rotiere wie ich das gemacht habe, steht noch immer im linken teilbaum das was kleiner ist und im rechten das was größer ist...

Nur, um sicher zu gehen. Wir reden hiervon:

vorher:

    A

   / \

  B   C

 / \

D   E

   /

  F


nachher:

    B

   / \

  D   A

 /   / \

F   E   C[/code]
Das ist deine "Rotation". Richtig?


Vorher ist D < B < F, nachher ist F < D < B.


aber trotzdem hat sich die reihenfolge verändert, und das muss sie auch, weil sonst eine rotation ja zu keinem ergebnis führen würde...
Entweder hast du nicht verstanden, was ich im letzten Beitrag geschrieben habe, oder du glaubst es mir nicht. Du darfst die Reihenfolge nicht ändern. Mit "Reihenfolge" meine ich die, die sich durch die Ordnungsrelation ergibt. Und deine Umformung ändert diese Reihenfolge in Bezug auf F und D bzw. B.


Deine Umformung ist keine Rotation. Sie macht den Baum kaputt.


Du musst mir nicht glauben. Aber wenn du es nicht tust, kann ich dir nicht helfen.

[Mobalasch]

ich glaubs dir schon. du verstehst sicher viel mehr davon als wie ich.

ich glaub ich habs nicht ganz verstanden. ich dachte eine einfache rotation wär zulässig. aber die erfüllt ja die avl bedingungen nicht also ist ne doppelrotation erforderlich.

[Klotzkopp]

ich dachte eine einfache rotation wär zulässig. aber die erfüllt ja die avl bedingungen nicht also ist ne doppelrotation erforderlich.

Ob du eine einfache oder eine Doppelrotation brauchst, hängt vom Balancewert des linken Kindknoten des Knotens ab, der -2 hat.

[Mobalasch]

aber ganz sicher bin ich mir noch nicht!

stimmt die rotation sicher nicht?

F war schon im orginalbaum das kleinste und nie größer als B oder D... und die relationen bleiben nach meiner rotation erhalten -> vorher C>A>E>B>D>F und nach "meiner" rotation ists noch immer so...

[Klotzkopp]

stimmt die rotation sicher nicht?

Nicht, wenn wir von meinem Beispiel ausgehen. Bei deinem ist das mangels Einrückung nicht wirklich zu erkennen.

Mein Beispiel war

    A

   / \

  B   C

 / \

D   E

   /

  F[/code]


F war schon im orginalbaum das kleinste und nie größer als B oder D... 
In meinem Beispiel ist D das kleinste Element.

[Mobalasch]

aber von D geht noch einmal nach links ein ast weiter zu F -> und nach links bedeutet kleiner, also ist F kleiner als D!

[Klotzkopp]

In meinem Beispiel hat D keine Kindknoten, weder links noch rechts. In deinem Beispiel kann man das nicht erkennen, weil du keine Code-Tags benutzt hast, und damit die Einrückung verloren geht. Wenn bei deinem Beispiel F der linke Kindknoten von D sein soll, ist deine Rotation natürlich richtig.

Allerdings hilft dir das nicht viel. Ich habe mein Beispiel ja absichtlich so gewählt, dass eine einfache Rotation nicht ausreicht.

[Mobalasch]

also dein originalcode hat so ausgeschaut:

Code:

A

/ \

B C

/ \

D E

/

F

und jetzt sagst du mir das F nicht links auf D folgt... dann ist aber diese "zeichnung" sehrsehrsehr schlecht gemacht!

[Klotzkopp]

also dein originalcode hat so ausgeschaut:

Code:

A

/ \

B C

/ \

D E

/

F

Nein, mein Beispiel sah so aus:

    A

   / \

  B   C

 / \

D   E

   /

  F[/code]

Ich weiß nicht, welchen Browser du benutzt, aber sowohl beim Internet Explorer als auch beim Firefox kann man da genau sehen, dass F der linke Kindknoten von E ist.


dann ist aber diese "zeichnung" sehrsehrsehr schlecht gemacht!
Willst du mich veräppeln? Du bist doch derjenige, der keine Codetags benutzt :confused: