¡Ayuda con preguntas sobre los árboles de Huffman! ¡urgente! ¡Se agregarán respuestas satisfactorias!
Árbol de Huffman
1. Términos básicos
1. Ruta y longitud de la ruta
Si hay una secuencia de nodos k1, k2. , ...., kj hace que kj sea el padre de kj 1 (1lt; = ilt; j), entonces se dice que la secuencia de nodos es la ruta de k1 a kj (como un nodo en el árbol a Una secuencia de nodos en orden desde uno de sus ancestros, o hasta uno de sus descendientes, incluido él mismo, se llama ruta. Dado que cada nodo en el árbol tiene solo un nodo padre, estos son dos La ruta única entre dos nodos, el número de ramas. que pasa de k1 a kj se llama longitud del camino entre estos dos puntos. Es igual al número de nodos -1.
Por ejemplo: la secuencia de nodos desde el nodo A hasta el nodo J
Las columnas son A, B, E, J.
La longitud del camino es 3.
8 10
4 5 3
2. El peso del nodo y la longitud de la ruta ponderada
Si es necesario, agréguelo al árbol Si se asigna un número real con un cierto significado a un nodo, entonces este número real se llama peso del nodo. La longitud de la ruta ponderada del nodo se define como la longitud de la ruta desde el. nodo raíz del árbol al nodo multiplicado por el nodo El producto de los pesos.
3. La longitud de la ruta ponderada del árbol
La longitud de la ruta ponderada del árbol se define como la suma de las longitudes de la ruta ponderada de todos los nodos de las hojas del árbol, generalmente registradas. como:
p>
n
WPL=∑ wili wi y li representan respectivamente el peso del nodo hoja ki y la longitud del camino desde ki al nodo raíz
i=1
p>Por ejemplo: WPL en la imagen de arriba = (4 5 3) * 3 (8 10) * 2 = 72
4. Árbol de Huffman
El árbol de Huffman también se denomina árbol binario óptimo, que es el árbol binario con la longitud de ruta ponderada más pequeña WPL entre todos los árboles binarios compuestos por n nodos de hoja ponderados.
Por ejemplo: hay cuatro nodos de hoja a, b, c, d, con pesos de 9, 4, 5, 2 respectivamente, que pueden formar tres árboles binarios diferentes (por supuesto, se pueden formar más árboles binarios). formarse) Vea la imagen a continuación:
9 4 5 2 WPL= (9 4 5 2)*2=40
4
2
5 9
WPL=(9 5)*3 2*2 4*1=50
4
2
5 9
WPL=(9 5)*3 2*2 4*1=50
9
5
4 2
WPL=9*1 5*2 (2 4)*3=37
Se puede demostrar que el último árbol binario es un árbol de Huffman.
2. Construir el árbol de Huffman
1. Construir n nodos hoja en n árboles binarios independientes, cada árbol binario tiene solo un nodo raíz.
2. Seleccione dos árboles binarios con los pesos más pequeños para fusionarlos en un árbol binario, use la suma de los pesos de los dos árboles binarios como el peso de este árbol binario y cancele los dos binarios originales. árboles.
3. Repita el paso 2 hasta que solo quede un árbol binario.
Por ejemplo: hay 6 nodos de hoja ponderados cuyos pesos son: 3, 6, 8, 5, 2, 2. Construya un árbol de Huffman y calcule el resultado de WPL.
1. Construya 6 árboles binarios
3 6 8 5 2 2
2Seleccione los dos árboles binarios con el peso más pequeño para formar un árbol binario
p>
2 2 El peso combinado es 4
3 6 8 5
3 6 8 5 4
2 2
Seleccione los dos árboles binarios con los pesos más pequeños para formar un árbol binario
7 6 8 5
3
2 2
Seleccione los dos árboles binarios con los pesos más pequeños para formar un árbol binario
7 11 8
3
5 6
2 2
Seleccione los dos árboles binarios con los pesos más pequeños para formar un árbol binario
15 11
8
5 6
3
2 2
Seleccione los dos árboles binarios con los pesos más pequeños para formar un árbol binario (el árbol de Huffman final)
8
5 6
3
2 2
WPL= (2 2)*4 3*3 (5 6 8) *2=16 9 38=63
Tarea: P221/9