Fragen zum AVL-Baum

[Fenixx]

Hi zusammen,

angenommen man hat folgende Aufgabe:

Gib jeweils für die Höhen 1, 2, 3 und 4 einen AVL-Baum an, der bei gegebener Höhe eine
minimale Anzahl von Knoten enthält. Notiere zu allen Knoten den Balancegrad.

Ist es nicht einfach so, wenn ich einen vollständigen Binärbaum pro Höhe angebe, diese Aufgabe erfüllt ist?
Höhe 1:

         2
   1          3

Höhe 2:

         4
   2          6
1    3     5     7

Usw.
Der Balancegrad jedes Knotens wär 0.

Gruß

 

[SlaterB]

bei gegebener Höhe eine minimale Anzahl von Knoten != vollständigen

 

[Fenixx]

Also wärs so korrekt?

Höhe 1:

         2
   1

b(2) = -1
b(1) = 0

Höhe 2:

         4
    2       5
1

b(4) = -1
b(2) = -1
b(5) = 0
b(1) = 0

Ist das so in Ordnung?

 

[SlaterB]

ich denke ja

 

[Fenixx]

Super. Vielen Dank für die Hilfe.

 

[SlaterB]

bei Höhe 3 und 4 wird es glaube ich interessanter,
da ist ein "usw." vielleicht unangebracht

aber ich habe die Definitionen eben erst nachgeschlagen, muss die auch nicht ganz verstehen

 

[Fenixx]

Höhe 3:

                                    5
                           3               8
                   2           4       7     9
               1

b(5) = -1
b(3) = -1
b(2) = -1
b(1) = 0
b(4) = 0
b(8) = 0
b(7) = 0
b(9) = 0

Höhe 4:

                             9
                    5               13
             3          7       11          15
         2      4     6  8   10  12     14    16
      1

Ich hoffe man kanns einigermaßen erkennen.
b(9) = -1
b(5) = -1
b(13) = 0
b(3) = -1
b(7) = 0
b(11) = 0
b(15) = 0
b(2) = -1
b(4,6,8,10,12,14,16) = 0
b(1) = 0

Das Sinn vom AVL-Baum ist halt eine Worst-Case-Laufzeit von Theta(n) zu vermeiden. Das Ganze passiert durch Balancierung des Baums.

Ich denke, dass das so richtig sein müsste.

 

[SlaterB]

bei Höhe 3 meine ich, kann z.B. die 7 noch wegfallen

 

[Fenixx]

Ich glaub ich weiß jetzt was du meinst.

Höhe 3:

                                    5
                           3               8
                   2           4              9
               1

Höhe 4:

                             9
                    5               13
             3          7       11     15
         2               8   10           
      1

Entsprechend noch die Balancegrad anpassen.

 

[wakoz]

....

Höhe 4:

                             9
                    5               13
              3          7       11     15
         2                8   10           
      1

Entsprechend noch die Balancegrad anpassen.

                             9
                    5               13
             [COLOR="Red"]2[/COLOR]          7       11     15
         1      [COLOR="#ff0000"]3 [/COLOR]       8   10

AVL Bäume dürfen nie unterschiedlich werden, Ideal ist jedes blatt ganz unten.
Die Knoten dürfen sich nie nach links und rechts betrachtet mehr als +-1 unterscheiden. sollte das nach einer änderung doch der fall sein, muss ein ausgleich passieren und erst danach darf weiter der baum weiter erweitert oder verkleinert werden.

 

[Fenixx]

Ja da hast du Recht.
Allerdings glaube ich nicht, dass dein Baum der Höhe 4 entspricht. So sollte es aussehen, denke ich:

                             9
                    5               13
              3          7       11     15
         2       4          8                16
      1

 

[wakoz]

Der Baum der Höhe vier hat kein bestimmtes aussehen, es kommt alleine darauf an in welcher reienfolge die die werte in den Baum eingefühgt werden.
AVL tree applet dort kanns du das einfügen mal ausprobieren und etwas rumspielen das tool ist klasse

 

[Civilazi]

Bei höheren Höhen hängt an den Zweigen immer ein extremaler AVL-Baum geringerer Höhe dran. So kannst du deine größeren Bäume leicht kontrollieren.