Trivialfrage zu AVL-Bäumen

[ModellbahnerTT]

Hallo zusammen,

zunächst hoffe ich, dass ich im richtigen Forum poste, falls nicht möchte ich mich dafür entschuldigen, wußte nicht wohin sonst.

Meine Aufgabenstellung lautet "Geben Sie alle AVL-B¨aume maximaler Höhe an, in denen die Zahlen 1 . . . 7 jeweils einmal vorkommen."

Was mich stutzig macht die das Wort "alle" nun dazu direkt die 1.Frage: Der AVL-Baum zeichnet sich ja dadurch aus, (wikizitat "dass sich für jeden Knoten k die Höhen h1 und h2 der beiden Teilbäume um höchstens 1 unterscheiden"

Das heißt doch, dass der Baum bei 7 Einträgen max. die höhe 3 haben kann oder?
Ich meine mehr als 3 ginge meiner Auffassung nach nicht.

Kann es sein, dass hiermit eher gemeint ist, dass ich verschiedene "Darstellungen" also den Baum mit höhe 3 mit jeweils verschiedenen eingaben machen soll?

Der Baum ist ganz schön tricky, habe hier ein tolles applet dazu gefunden AVL tree applet

Dann noch eine Trivialfrage, wie ich zum knoten komme ist doch egal oder muss die höhe unbedingt auf "direkten weg" durchlaufen werden sprich z.B. nur von der wurzel aus ganz nach links oder rechts oder ist die verzweigung egal? Glaube die ist egal.

Besten Dank schonmal.

 

[Ezra]

Das heißt doch, dass der Baum bei 7 Einträgen max. die höhe 3 haben kann oder?

Die maximale Höhe ist 4. Man fängt mE bei Eins mit Zählen an.
Als Beispiel:

            3
   2                 5
1                  4    6
                            7

Kann es sein, dass hiermit eher gemeint ist, dass ich verschiedene "Darstellungen" also den Baum mit höhe 3 mit jeweils verschiedenen eingaben machen soll?

Wenn die Eingabereihenfolge der Elemente variiert, kann auch ein anderer Baum entstehen. Keine Ahnung, ob ich Dich hier richtig verstehe. Es gibt jedenfalls mehrere korrekte AVL-Bäume mit denselben Elementen und der Höhe 4. Aber alle Eingaben durchzugehen, wäre viel zu aufwändig. Am besten rotierst Du einen vorhandenen korrekten Baum hin und her und erzeugst so alle möglichen Variationen.
Oder Du schreibst Dir ein Programm, das Dir die Varianten ermittelt.

Dann noch eine Trivialfrage, wie ich zum knoten komme ist doch egal oder muss die höhe unbedingt auf "direkten weg" durchlaufen werden sprich z.B. nur von der wurzel aus ganz nach links oder rechts oder ist die verzweigung egal? Glaube die ist egal.

Wie? Du hast doch nur einen möglichen Weg vom tiefsten Blatt bis zur Wurzel. Oder versteh ich was falsch?

 

[ModellbahnerTT]

Die maximale Höhe ist 4. Man fängt mE bei Eins mit Zählen an.

Wie? Du hast doch nur einen möglichen Weg vom tiefsten Blatt bis zur Wurzel. Oder versteh ich was falsch?

Also erstmal besten Dank.
Irritieren tut mich folgendes Wikipedia-Beispiel zur höhe des Baumes:
Höhe (Graphentheorie) ? Wikipedia)
Oder gilt bei AVL-Bäumen eine andere "Zählweise"?

Mit den mögichen Weg vom tiefsten Blatt bis zur Wurzel meine ich, wenn die 7 z.B. links neben der 4 gestanden hätte (mal angenommen, weiß, dass es sortiermässig nicht geht), wäre dann die Höhe gleich?

Besten Dank nochmal.

 

[Ezra]

Irritieren tut mich folgendes Wikipedia-Beispiel zur höhe des Baumes:
Höhe (Graphentheorie) ? Wikipedia)
Oder gilt bei AVL-Bäumen eine andere "Zählweise"?

Stimmt, dort wäre die maximale Höhe 3. Ich habe aber mal in meine Unterlagen für Algorithmen und Datenstrukturen geguckt und dort fangen wir mit Zählen bei Eins an. Also die Anzahl der Kanten bis zum tiefsten Blatt plus Eins (ergo wäre die Höhe 4). Ich schätze, das ist eine Festlegungssache. Frag am besten Deinen Prof - oder für wen auch immer Du das machen musst -, wie er das handhabt.

Mit den mögichen Weg vom tiefsten Blatt bis zur Wurzel meine ich, wenn die 7 z.B. links neben der 4 gestanden hätte (mal angenommen, weiß, dass es sortiermässig nicht geht), wäre dann die Höhe gleich?

Ja. "Die Höhe eines Baumes ist die maximal auftretende Tiefe."

 

[ModellbahnerTT]

Danke nochmal für eine Hilfe,

also das mit der Höhe ist in unseren Fall 4 aber ist ja auch irrelevant.
Stehe leider immer noch vor folgendem Problem.

Geben Sie alle AVL-B¨aume maximaler Höhe an, in denen die Zahlen 1 . . . 7 jeweils einmal vorkommen.

Tipp vom Tutor waren, dass es über 10 waren.

Meine Grundidee ist folgendes:

Es gibt nur zwei Arten und diese werden dann jeweils gespiegelt

            3
   2                 5
1                  4    6
                            7

            3
   2                 5
1                  4    6
                  X

Kann das sein? Kollegen die die Aufgabe gelößt haben, meinten 16 möglichkeiten gehabt zu haben.
Ich glaube aber es geht hier um die beiden grundteile oben und die jeweils gespiegelt mit verschiedenen zahlen, kann das sein?

Wenn ja, könnt ihr mir vielleicht einen tipp geben, wie ich die alle ausfindig machen kann?
Hab durch geschicktes ausprobieren 7 Stück gefunden.

Nachtrag: OK ich denke eine Sache habe ich außer Acht gelassen, das jeweils unterste (ausschlaggebende Blatt) kann ja jeweils wieder rechts oder links sein dem entsprechend habe ich das oben angegebene mal 2 macht mit spiegelung 8 Möglichkeiten und dann glaube ich, sind es 2 werte pro Möglichkeit.
Nachtrag 2: Jetzt bin ich konfus, es kann ja auch noch die möglichkeit geben:

Fall 1

            3
   2                 5
1                  4    6
                  X

Fall 2

            3
   2                 5
       Y          4    6
                 X

Und wenn ich dann alles spiegel usw. komme ich auf 16 Fälle, meint ihr das ist das gemeinte?

 

[Ezra]

Sind die Zahlen bei Dir nur Platzhalter? Falls ja, stimmt es so, wie Du Dir das gedacht hast.