Huffman Tree für Frequenzen von i-ten Alphabeten ist 2 ^ i? - Algorithmus, Datenstrukturen, Baum, Huffman-Code

Ich bereite mich auf DS vor. Ich lese meine Notizen. Eines dieser Probleme ist nicht gut ausgebildet. Jeder könnte es für mich beschreiben?

Angenommen in einem Text sind die Häufigkeiten der englischen Alphabete 2^i (^ bedeutet Macht). Wie hoch ist der Huffman-Baum für diese Charaktere?

Ich brauche jemanden, der mir hilft ...

Antworten:

Die Höhe ist n - 1, woher n ist die Größe des Alphabets (nennen wir es h(n)).

Beweis:

1. Basisfall. n = 2die Höhe ist eins.

2. Schritt: 2 ^ n > 2 ^ 0 + ... + 2 ^ (n - 1). Also, der Baum für ein Alphabet der Größe n sieht so aus: Eine Wurzel hat zwei Kinder: das a Blatt mit dem n-te Zeichen (die häufigste) und eine Wurzel eines Baumes für ein Alphabet der Größe n - 1. Es bedeutet, dass seine Höhe ist h(n) = h(n - 1) + 1 = (n - 2) + 1 = n - 1.

P.S. Ich nehme an, dass die Höhe die Anzahl der Kanten im längsten Pfad zu einem Blatt ist. Wenn wir die Höhe als eine Anzahl von Ecken definieren, lautet die Antwort: n.