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
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?
bandchef hat dieses Bild (verkleinerte Version) angehängt: