Vollständige Induktion Avl Baum

Question

Hallo, ich komme bei einer Aufgabe nicht weiter.. Man muss durch vollständige Induktion beweisen, dass ein AVL Baum höchstens die Höhe 2^h -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) \)
?

Comments

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

Answer 1

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.

Comments

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