La codificación de Huffman usa la probabilidad de ocurrencias de cada valor, para construir un árbol donde los valores son las hojas. La longitud de la ruta desde la raíz a una hoja es mínima para los valores más probables.
¿El árbol construido (ignorando la asignación de 0s y 1s a izquierda y derecha) siempre está equilibrado? (Equilibrado: la profundidad de la subtítulo izquierda y derecha de cada nodo difiere como máximo en 1)
Apoyo con prueba matemática sería muy apreciado :)
Respuestas
1 para la respuesta № 1No. Considera las frecuencias 1, 1, 2, 4
. Se generará un árbol como el siguiente:
0 para la respuesta № 2
No. Incluso los ejemplos básicos que se muestran, por ejemplo, en la página de Wikipedia, tienen codificaciones con tres longitudes diferentes en un solo árbol.