Informatiker Board | Druckvorschau: Höhe eines Heaps

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Höhe eines Heaps (http://www.informatikerboard.de/board/thread.php?threadid=1203)

Geschrieben von bandchef am 28.04.2012 um 17:43:

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?

Geschrieben von Karlito am 03.05.2012 um 10:43:

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 [latex]h(n)[/latex]

in Abhängigkeit von der Anzahl der Knoten [latex]n[/latex]

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