Diferencia entre revisiones de «Codificación Huffman»
Contenido eliminado Contenido añadido
m Revertidos los cambios de 193.144.61.240 (disc.) a la última edición de 79.145.44.102 |
m (Bot) Correcciones ortográficas |
||
Línea 179:
Cada nodo del árbol puede ser o bien un [[nodo hoja]] o un [[nodo interno]]. Inicialmente se considera que todos los nodos de la lista inicial son nodos hoja del árbol. Al ir construyendo el árbol, los nodos internos tendrán un '''peso''' y dos [[nodos hijos]], y opcionalmente un enlace al [[nodo padre]] que puede servir para recorrer el árbol en ambas direcciones. Por convención el bit '0' se asocia a la rama izquierda y el bit '1' a la derecha. Una vez finalizado el árbol contendrá <math>n</math> [[nodos hijo]] y <math>n-1</math> [[nodos internos]].
El proceso de construcción del árbol comienza formando un nodo intermedio que agrupa a los dos nodos hoja que tienen menor '''peso''' (frecuencia de aparición). El nuevo nodo intermedio tendrá como nodos hijos a éstos dos nodos hoja y su campo '''peso''' será igual a la suma de los '''pesos''' de los nodos hijos. Los dos nodos hijos se eliminan de la lista de nodos, sustituyéndolos por el nuevo nodo intermedio. El proceso se repite hasta que sólo quede un nodo en la lista.
El algoritmo de construcción del árbol puede resumirse así:
| |||