|
  |
 binärbaum, maximale höhe ... |
|
|
| 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?!
__________________
I'm 71% Megatron!
|
|
28.01.2008 15:51 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Was ist denn ein Binärbaum für ein Alphabet?
|
|
|
28.01.2008 16:35 |
|
|
|
|
das war mal ausnahmsweise wörtlich aus der aufgabe abgeschrieben ...
| Zitat: |
| Beweise, dass die Tiefe des Binärbaums B für ein beliebiges Alphabet mit n Buchstaben im ungünstigsten Fall n - 1 beträgt. |
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
__________________
I'm 71% Megatron!
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von JROppenheimer: 28.01.2008 16:51.
|
|
|
28.01.2008 16:48 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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?
|
|
|
28.01.2008 17:13 |
|
|
|
|
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?!
__________________
I'm 71% Megatron!
|
|
|
28.01.2008 17:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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:31 |
|
|
|
|
sehr gutes argument 
ich danke Dir!
__________________
I'm 71% Megatron!
|
|
|
28.01.2008 17:37 |
|
|
|
|
|
|
|
|
