binärbaum, maximale höhe ... |
| 28.01.2008, 15:51 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | binärbaum, maximale höhe ... Es geht um Folgendes: Ich arbeite im Moment mit den Huffman Code. Jetzt sol lich zeigen, dass die Tiefe eines Binärbaums B für ein beliebiges Alphapet von n Buchstaben im ungünstigsten Fall n-1 beträgt. Ich spiele jetzt damit rum und irgendwie ist mir das schon klar, dass das so ist, aber ich bin nicht sicher, wie ich das beweisen soll. Induktiv, argumentativ, anschaulich? Für einen Binärbaum gilt doch, jeder Knoten ist Vater von höchstens einem Kindknoten. Weiterhin gilt, dass ein Knoten immer Vater von: 1. zwei Knoten 2. einem knoten und einem blatt oder 3. zwei blättern ist, richtig?! Ich dachte jetzt an einen Widerspruch, indem ich sage, wäre die Tiefe des Baums >n-1, dann würde ein Knoten existieren, der nur Vater eines Knotens ist, und das ist ja nicht erlaubt, bzw. wäre es dann kein Binärbaum mehr. Wie klingt das?! |
||
|
|
|||
| 28.01.2008, 16:35 | Auf diesen Beitrag antworten » | ||
| Tobias | Was ist denn ein Binärbaum für ein Alphabet? |
||
| 28.01.2008, 16:48 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | das war mal ausnahmsweise wörtlich aus der aufgabe abgeschrieben ...
Angenommen, ich habe ein Alphabet, und einen Text Dann gibts ne Häufigkeitstabelle für die Buchstaben aus dem Alphabet. und Anhand dieser Häufigkeitstabelle kann man einen Binärbaum erstellen. Dabei sind Buchstaben Blätter deren Gewicht ihre Häufigkeit ist. Bei der Huffmankodierung beginnt man mit einer sortierten Menge von Bäumen (jeder Buchstabe ist erstmal ein eigener Baum). Dann werden solange die leichtesten Bäume zu einem neuen mit neuem Gewicht=Summe der Gewichte der Teilbäume links und rechts, zusammengefügt, bis ein einzelnder Baum entsteht. das ist die sehr kurzfassung der huffmankodierung, ich hoffe du verzeihst mir etwaige ungenauigkeiten. Angenommen ich habe ein Alphabet Z = {A B D} und einen Tex ABBDDD Dann ergäben sich hieraus 3 Bäume A B D 1 2 3 Jetzt werden die beiden leichten Bäume zu einem "verschmolzen" und die Liste der Bäume neu sortiert (ist hier eigendlich nicht nötig) Da das mit den Indents hier net so wirklich funktioniert hat, lasse ich das mal. Ich bin mir fast sicher, dass Du weisst, was die HuffmanKodierung ist, wäre ein Wunder wenn Du das nicht weisst 
Tobiaspedia
|
||
| 28.01.2008, 17:13 | Auf diesen Beitrag antworten » | ||
| Tobias | Naja, dir ist klar wie ein Huffman-Tree "gebaut" wird, dir ist auch klar, wie ein Huffman-Tree mit Höhe n-1 aussehen muss.. also wo genau hapert es noch? Du sollst zeigen, dass es Huffman-Trees geben kann, die so "entartet" sind. Der Trick ist wohl -wenn ich das richtig sehe-, dass der zusammengeklebte Baum immer leichter ist als der nächste Buchstabe. Daraus kann man also ableiten, dass der i't-leichteste Buchstabe schwerer sein muss als die Summe der Vorgänger. Oder sehe ich da was falsch? |
||
| Anzeige | |||
|
|
|||
| 28.01.2008, 17:21 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | So hab ich das auch gemacht. Ich fragte mich jetzt nur, wie ich da was beweisen muss. Also die Tatsache, dass es gar net schlechter geht. Wenn ich n bspAlphabet nehme und eben nach dem genannten Prinzip die Häufigkeiten verteile. Dann bekomme ich ja eben, GENAU SO einen BinärBaum der Tiefe n-1. Das hab ich ja auch alles geschafft, aber mir ist irgendwie nicht klar, wie ich beweisen soll, dass es gar nicht mehr als n-1 sein kann. Versteh mich nich falsch, es harpert gar nicht daran, dass ich nich mit Huffman umgehn kann. Aber ich verstehe de facto nicht, wie ich das "beweisen" soll. Reicht es, wenn ich das argumentativ zeige?! Was denkst Du?! |
||
| 28.01.2008, 17:31 | Auf diesen Beitrag antworten » | ||
| Tobias | Also du musst zeigen: 1.) Für jedes mögliche Alphabet mit n Buchstaben gibt es ein Wort, das ein Huffman-Tree der Höhe n-1 zur Folge hat. Die Konstruktion hast du ja schon hinbekommen. Dann fehlt noch 2.) Ein Huffman-Tree mit Höhe n-1 ist maximal entartet, d.h. die Höhe n ist nicht möglich. Jeder Huffman-Baum hat n Blätter. Die Höhe n des Baumes ist nur möglich, wenn auf jeder Ebene genau ein Blatt existieren würde. Dies ist durch die erste Konstruktion (Verkleben von zwei Buchstaben) jedoch schon nicht mehr möglich. Dort sind nämlich immer zwei Blätter auf einer Ebene. |
||
| 28.01.2008, 17:37 | Auf diesen Beitrag antworten » | ||
| JROppenheimer | sehr gutes argument 
ich danke Dir! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
