Informatiker Board | Theoretische Informatik

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Höhe eines Heaps

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

bandchef
Mitglied

Dabei seit: 06.10.2009
Beiträge: 28

Höhe eines Heaps

Zitatantwort auf diesen Beitrag erstellen

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:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von bandchef: 28.04.2012 17:44.

28.04.2012 17:43

Nehmen Sie bandchef in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Karlito: 03.05.2012 15:08.

03.05.2012 10:43

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

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