# Fragen zum AVL-Baum



## Fenixx (1. Jun 2009)

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 (1. Jun 2009)

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


----------



## Fenixx (1. Jun 2009)

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 (1. Jun 2009)

ich denke ja


----------



## Fenixx (1. Jun 2009)

Super. Vielen Dank für die Hilfe.


----------



## SlaterB (1. Jun 2009)

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 (1. Jun 2009)

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 (1. Jun 2009)

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


----------



## Fenixx (1. Jun 2009)

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 (1. Jun 2009)

Fenixx hat gesagt.:


> ....
> 
> Höhe 4:
> 
> ...




```
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 (2. Jun 2009)

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 (2. Jun 2009)

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 (3. Jun 2009)

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.


----------

