Höhe eines Heaps

28.04.2012, 17:43	Auf diesen Beitrag antworten »
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?


03.05.2012, 10:43	Auf diesen Beitrag antworten »
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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »