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

Question

Aufgabe:

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

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

Problem/Ansatz:

Ich werde sehr dankbar, dass Sie mir ein Paar Tipps geben, wie ich das lösen kann.

Comments

Das ist theoretische Informatik. AVL-Bäume werden in der Praxis nicht verwendet, stattdessen findet man gelegentlich Rot-Schwarz-Bäume. Standardmäßig wird Hashing verwendet.

---

Vom Duplikat:

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

Stichworte: avl,baum

Frage:

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.)


Problem/Ansatz:

Ich werde sehr dankbar, dass Sie mir ein Paar Tipps geben, wie ich das lösen kann.

---

Deine Frage (gemäss Tschaka) Informatik (und ev. fachkundige Hilfe) findest du nun hier https://www.stacklounge.de/7156/zeige-vollstandiger-induktion-mindestens-knoten-enthalt . Sie darf selbstverständlich in der Stacklounge auch beantwortet werden ;) Gleiches Login wie hier. Danke.

Beachte auch die bereits vorhandenen "ähnlichen Fragen" in beiden Lounges. Bsp. https://www.mathelounge.de/745430/vollstandige-induktion-avl-baum Vielleicht hast du dann ja selbst einen Tipp an künftige Studis.

---

Danke dir Lu

Answer 1

Das hier https://www.mathelounge.de/745430/vollstandige-induktion-avl-baum unbrauchbar?

Comments

Ich komme damit trotzdem nicht weiter.

---

Ich bitte um Ihre Hilfe!!!

---

Warum keiner reagiert?

---

Bitte reagiere inhaltlich direkt auf die Antwort hier: https://www.mathelounge.de/745430/vollstandige-induktion-avl-baum .

Problem bei den Potenzgesetzen oder beim Zeichnen dieser Bäume oder .. ?