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 . Ich weiß, wenn ich einen Heap zeichne, dann entspricht die Höhe des Heaps in der Tat . 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: 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 ist. edit: vollständig Induktion ist bestimmt nicht notwendig. VG, Karlito |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|