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-mindes… 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² , also 2^(h-1) * 4 =  2^(h-1) * 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¹ 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