# Algorithmen und Datenstrukturen: Blatt 8

## Aufgabe 1

Einen AVL-Baum der Höhe 10 auf ein A4-Blatt zu zeichnen
ist deshalb schwierig oder zumindest überaus aufwendig,
da ein solcher Baum mindestens 123 Knoten besitzt.
Dies geht aus der Formel für die maximale Tiefe d des
Baumes zu einer bestimmten Knotenzahl n hervor:
$d = \frac{1}{log(\frac{\sqrt 5 +1}{2})}\cdot log(n)$.
Formt man diese Formel nach n um,
erhält man die Mindestanzahl der Knoten abhängig von der Tiefe:
$n = (\frac{\sqrt 5 + 1}{2})^{d}$.
Für einen Baum der Höhe 10 ergibt das:
$n = (\frac{\sqrt 5 + 1}{2})^{10} \approx 123$ Knoten.

## Aufgabe 2


## Aufgabe 3

### 3a)

Induktionsanfang:
$h = 0: 2^0-1 = 0$.
Zusätzlich:
Ein vollständiger, nicht-leerer Binärbaum hat immer $2^h$ Blätter und
insgesamt $\sum_{i=0}^h 2^i$ Knoten.
Die inneren Knoten sind diejenigen, die nicht Blätter sind,
also gilt: Anzahl der inneren Knoten = Anzahl Knoten - Anzahl Blätter.
Bei Höhe $h = 0$ hat dieser Baum $2^0 = 1$ Blatt und $\sum_{i=0}^0 2^i = 1$ Knoten.
Damit hat er $1-1=0=2^0-1$ innere Knoten.
Dies kann man sich auch leicht veranschaulichen:
Da ein Baum der Höhe 0 nur aus der Wurzel selbst besteht,
wird diese als Blatt und nicht als innerer Knoten angesehen.

Induktionsvoraussetzung:
Die Aussage gilt für ein beliebiges, aber festes $h$.

Induktionsschritt: $k = h+1$: Betrachtet wird nun ein Baum der Höhe $k$:

- Anzahl Knoten insgesamt: $\sum_{i=0}^k 2^i$
- Anzahl Blätter: $2^k$

$\Rightarrow$ Anzahl innerer Knoten: $(\sum_{i=0}^k 2^i) - 2^k=
(\sum_{i=0}^h 2^i) + 2^k - 2^k = \sum_{i=0}^h 2^i = 2^{h+1}-1 = 2^k-1$
$\Box$

### 3b)

Aus Aufgabe 3a) geht hervor, dass die Anzahl der inneren Knoten eines
vollständigen nicht-leeren Binärbaums mit der Höhe h $2^h-1$ beträgt.
Zu zeigen ist also, dass ein derartiger Baum $2^h$ Blätter besitzt.

Induktionsanfang: $h=0$:
Da ein Baum der Höhe 0 nur aus der Wurzel selbst besteht,
wird diese als Blatt und nicht als innerer Knoten angesehen.
Damit besitzt ein Baum der Höhe 0 $2^0 = 1$ Blätter.

Induktionsvoraussetzung:
Die Aussage gilt für ein beliebiges, aber festes $h$.

Induktionsschritt: $k = h+1$: Betrachtet wird nun ein Baum der Höhe $k$:

### 3c)

Zu zeigen: Für jeden nicht-leeren Binärbaum gilt,
dass er genau einen Knoten mehr als Kanten hat.
Anschaulich betrachtet ergibt diese Aussage Sinn, da zu jedem Knoten
genau eine Kante führt, außer zum Wurzelknoten.
Die Behauptung anders formuliert:
Zu jedem Baum mit $n$ Knoten existieren genau $m = n-1$ Kanten.
$\Rightarrow n=m+1.$

Induktionsanfang:
Sei $n = 1$. Ein Baum mit einem Knoten enthält nur den Wurzelknoten.
Wie bereits beschrieben, führt zu diesem keine Kante.
Damit gilt, dass dieser Baum $0 = 1-1 = n-1$ Kanten hat.

Induktionsvoraussetzung:
Die Behauptung gilt für ein beliebiges, aber festes n.

Induktionsschritt: $k = n+1$. Wir fügen also einen k-ten Knoten ein:
Es gilt aber, da $k = n+1$ und (Nach IV.) $n = m+1$,
dass $k = (m+1)+1$. $\Rightarrow (m+1) = n = k - 1$.
Wenn wir also einen Knoten einfügen, erhöht sich auch die Anzahl der Kanten um 1.
Damit ist die Behauptung nach wie vor wahr.
$\Box$

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`