Informatiker Board | Theoretische Informatik | Höhe eines Heaps

Informatiker Board » Themengebiete » Theoretische Informatik » Höhe eines Heaps » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge
Karlito	Hallo, Beweis durch Beispiel reicht natürlich nicht. Ich würde folgendermaßen vorgehen: - Beschreibung des Inserts (mit allen Fällen) - Beschreibung des Löschvorgangs (mit allen Fällen) - Änderung = Löschen + wieder Einfügen (der Einfachheit halber) - mathematische Beschreibung der Höhe des Baums in Abhängigkeit von der Anzahl der Knoten und dann vollständige Induktion, dass die Beschreibung, welche Du dir ausgedacht hast, immer $[latex]h(n) \leq \lfloor log(n) \rfloor [/latex]$ ist. edit: vollständig Induktion ist bestimmt nicht notwendig. VG, Karlito
bandchef	Höhe eines Heaps Vollständige Teilaufgabe: Zeigen Sie die Aussage: Ein Heap mit n-Elementen hat die Höhe $[latex] \lfloor log(n) \rfloor [/latex]$ . Ich weiß, wenn ich einen Heap zeichne, dann entspricht die Höhe des Heaps in der Tat $[latex] \lfloor log(n) \rfloor [/latex]$ . Ich hab unten ein Bild von meinem Heap. Wie man sehen kann hat dieser Heap 7 Elemente, also n=7. Wenn ich nun die Höhe des Heaps berechnen will, gilt: $[latex] h=\lfloor log_2(n) \rfloor = \lfloor log_2(7) \rfloor = 2 [/latex]$ Meine Frage: Wie aber zeigt man nun diese Aussage? Oder bin ich schon fertig? bandchef hat dieses Bild (verkleinerte Version) angehängt: