0 Daumen
1,1k Aufrufe

Hallo, ich komme bei einer Aufgabe nicht weiter.. Man muss durch vollständige Induktion beweisen, dass ein AVL Baum höchstens die Höhe 2h -1 hat.

Vielen Dank für die Hilfe

\( n(1)=1 \)
\( n(2)=2 \)
Beachte \( n(h+1)=1+n(h)+n(h-1) \)

\( n(h) \leq 2^{h}-1 \)
IA:

h=1
\( n(1)= 1 \leq 2^{1}-1 \)

\( h=2 \)
\( n(2)=2  \leq 3=2^{2}-1 \)

Ib:
Es Existiert ein h \(  \in \mathbb{N}: n(h) \leq 2^{n}-1 \)

Iv:
Zu Zeigen: h = h+1
\( n(h+1) \leq 2^{h+1}-1 \)

IS:
\( \quad n(h+1)=1+n(h)+n(h-1) \)
?

Avatar von
Solltet ihr hier heute nochmals eine Nachfrage beantworten, bitte auch bei https://www.stacklounge.de/7156/zeige-vollstandiger-induktion-mindestens-knoten-enthalt#c7161 verlinken. Vielleicht ist das dann ja doch lösbar für malin. Danke

1 Antwort

0 Daumen
 
Beste Antwort

Es sei h∈ℕ mit: Formel gilt für alle nat. Zahlen ≤ h.

Dann:

n(h+1) = 1+n(h)+n(h-1)

         ≤ 1 + 2^h - 1 + 2^(h-1)-1

     =  2^h - 1 + 2^(h-1)

     = 2*2^(h-1) + 2^(h-1) - 1

     = 2^(h-1) * ( 2+1) - 1

      = 2^(h-1) * 3 - 1

      ≤ 2^(h-1) * 4 - 1

      = 2^(h+1) - 1.

Avatar von 287 k 🚀

du bist der beste ich danke dir

verstehe nur noch nicht so ganz diese Schritte:

= 2^(h-1) * 3 - 1

 ≤ 2^(h-1) * 4 - 1

= 2^(h+1) - 1.


was hast du da genau gemacht, dass du am Ende auf 2^(h+1) - 1 kommst

wenn ich ehrlich bin verstehe ich das auch nicht, sry bin noch nicht so geübt in Ungleichungen

= 2*2^(h-1) + 2^(n-1) - 1

= 2^(h-1) * ( 2+1) - 1

Na ja, 3 < 4 also auch

2^(h-1) * 3 - 1

≤ 2^(h-1) * 4 - 1

und 4 = 2^2 , also 2^(h-1) * 4 =  2^(h-1) * 2^2 = 2^(h+1)

Exponenten addieren !

okay danke das macht schonmal Sinn für mich

wenn ich ehrlich bin verstehe ich das auch nicht, sry bin noch nicht so geübt in Ungleichungen

= 2*2^(h-1) + 2^(n-1) - 1

= 2^(h-1) * ( 2+1) - 1

Also das n war falsch, dass muss natürlich h heißen

vorher war es =  2^h - 1 + 2^(h-1)

und dann habe ich aus dem 2^h einfach nur

2^(h-1) * 2^1 gemacht, dann gibt es

= 2*2^(h-1) + 2^(h-1) - 1

und dann das 2^(h-1) ausgeklammert gibt

= 2^(h-1) * ( 2+1) - 1

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community