0 Daumen
1,2k 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.)


Problem/Ansatz:

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

Avatar von

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

1 Antwort

0 Daumen
Avatar von

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community