0 Daumen
602 Aufrufe

Aufgabe:

Zeige mit vollständiger Induktion, dass ein AVL–Baum der Höhe h mindestens Fh+2 - 1 Knoten enthält.

Hinweis: Fn beschreibt die n-te Fibonacci-Zahl mit F0 = 0, F1 = 1 und Fn=Fn -1+ Fn-2

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Vollständige Induktion – AVL Baum mit Höhe h

Zu zeigen: Ein AVL–Baum der Höhe \(h\) hat mindestens \(F_{h+2} - 1\) Knoten.

Induktionsbasis:

Für \(h = 0\) (der geringstmögliche Höhe, da Höhe des leeren Baumes als \(-1\) definiert ist):
\( F_{0+2} - 1 = F_2 - 1 = 1 - 1 = 0\)
Ein AVL-Baum der Höhe \(0\) hat genau einen Knoten (\(0\) Knoten, falls der Baum leer ist), was der Behauptung entspricht.

Für \(h = 1\):
\( F_{1+2} - 1 = F_3 - 1 = 2 - 1 = 1\)
Ein AVL-Baum der Höhe \(1\) hat mindestens zwei Knoten, was ebenfalls der Behauptung entspricht, da ein AVL-Baum mit einer Höhe von \(1\) mindestens einen Wurzelknoten und mindestens einen Kindknoten besitzen muss.

Induktionsannahme:

Angenommen, die Aussage gilt für alle Höhen bis \(h\), d.h. ein AVL-Baum mit Höhe bis \(h\) hat mindestens \(F_{h+2} - 1\) Knoten.

Induktionsschritt:

Zu zeigen ist, dass die Aussage auch für die Höhe \(h + 1\) gilt.

Ein AVL-Baum der Höhe \(h+1\) muss aus zwei geringer hohen AVL-Bäumen aufgebaut sein, deren Höhenunterschied höchstens 1 beträgt (aufgrund der AVL-Bedingung). Diese zwei AVL-Bäume können Höhen \(h\) und \(h-1\) haben.

Gemäß der Induktionsannahme hat der Baum der Höhe \(h\) mindestens \(F_{h+2} - 1\) Knoten und der Baum der Höhe \(h-1\) mindestens \(F_{h+1} - 1\) Knoten.

Rechnung:

\( F_{(h+1)+2} - 1 = F_{h+3} - 1\)

Wir verwenden die Eigenschaft der Fibonacci-Zahlen: \(F_{h+3} = F_{h+2} + F_{h+1}\). Das setzen wir in die obige Formel ein:

\( F_{h+3} - 1 = (F_{h+2} + F_{h+1}) - 1\)

Der AVL-Baum der Höhe \(h+1\) enthält:

- Einen Wurzelknoten
- Mindestens \(F_{h+2} - 1\) Knoten vom linken oder rechten Unterbaum der Höhe \(h\)
- Mindestens \(F_{h+1} - 1\) Knoten vom anderen Unterbaum der Höhe \(h-1\)

Zusammengefasst ergibt er:
\( 1 + (F_{h+2} - 1) + (F_{h+1} - 1) = F_{h+2} + F_{h+1} - 1\)

Was durch die Fibonacci-Relation genau \(F_{h+3} - 1\) ergibt.

Damit ist gezeigt, dass auch für die Höhe \(h + 1\) die Anzahl der Knoten in einem AVL-Baum mindestens \(F_{h+3} - 1 = F_{(h+1)+2} - 1\) entspricht.

Da die Aussage für die Basisfälle \(h = 0\) und \(h = 1\) sowie unter der Annahme, dass sie für ein beliebiges \(h\) gilt, auch für \(h+1\) bewiesen werden konnte, folgt nach dem Prinzip der vollständigen Induktion, dass ein AVL-Baum der Höhe \(h\) stets mindestens \(F_{h+2} - 1\) Knoten enthält.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community