Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Übungs/Klausuraufgabe “Schranken für Codewortlängen”
Kriege den Induktionsbeweis für die untere untere Schranke nicht hin. Also wie beweist man NlogN <= L1 + L2 + … + LN
bzw.: logN <= mittlereHöhe(Binärbaum mit N Blätter)
Falls den jemand hat, bitte posten!
Also auf induzieren hab ich keine Lust. Untere Grenze wäre der Huffman Baum der optimal ausbalanciert ist. So ein ausbalancierter Baum mit n Blättern hat mindestens Höhe log n. Da hier aber nach der Wortlänge über alle Wörter gefragt ist (und es gibt in dem Baum ja genau n Wörter) so ist die untere Grenze = Höhe * Anzahl der Wörter = n log n. Das es nicht besser geht, liegt am Shannon. Die Herleitung für die Binärbaumhöhe steht im Schöning aber auch irgendwo beim Strehl in den Folien.
Die obere Grenze wäre der entartete Huffman Baum - sprich immer nur ein Blatt und dann eine Ebene darunter. Dort wieder Blatt und neue Ebene. Dieser Baum hat n-1 Ebenen. Er hat aber keine n Ebenen weil auf der untersten Ebene zwei Blätter hängen. Das wäre also die Summe von i = 1 bis n-1 über i. Für die unterste Ebene kommen aber noch ein Wort mit (n-1) dazu weils da zwei Blätter gibt. Macht zusammen (n(n-1) / 2 ) + ( n -1 ) und das ergibt (n²+n-2) / 2.
Das wußte ich schon… Ich will die Induktion sehen!
Also gut.
Binärer Baum mit einem Knoten hat Höhe 1. Pro Knoten kann es maximal 2 Kanten geben.
Pro Kante entsteht entweder ein Blatt oder ein neuer Knoten.
Im Falle eines “perfekten” binären Baumes entsteht pro neuer Knotenebene k
2^k neue Kanten. Ein solcher Baum hätte also 2^k Blätter bei einer Höhe k.
In dem Fall gilt log(#Blätter) = Höhe
Für alle anderen Bäume kann es vorkommen, dass es auch Blätter auf anderen Ebenen als auf der untersten gibt.
In dem Fall sind auf der untersten Ebene aber weniger als 2^k Blätter. Macht also log(#Blätter) <= Höhe.