1.a) Un árbol de Huffman siempre es completo.
Para mi es verdadero porque que sea completo implica que todos los nodos tengan el mismo grado y creo que esto se cumple para el árbol binario de huffman ya que cuándo se construye se toman los caracteres de a pares de la tabla de frecuencias...
gracias! todo esto me sirve rindo mañana!
Estuve leyendo acerca de los árboles Completos y Llenos. Los apuntes de Reinosa tienen definiciones muy diferentes a los de Zaffaroni, por lo que ahí está el gran problema, todos tenemos definiciones distintas.
Estuve buscando y entiendo que los de Enrique Reinosa está bien la definición de Completo, pero no tiene la de Lleno.
Por lo que busqué sería:
Árbol Completo: Es el que tiene desde la Raiz (Nivel 0) hasta el nivel h-1 absolutamente todos los nodos. Y en el nivel h puede haber desde 1 nodo hasta completar ese nivel. O sea al menos 2^h nodos hasta (2^h+1)-1.
Árbol Lleno: Aquel que todos los nodos tienen 0 o 2 nodos como salida.
Por lo que la afirmación:
1.a) Un árbol de Huffman siempre es completo.
Sería Falsa, ya que siempre es un árbol lleno, pero no tiene porqué ser completo.
(Para la definición de Zaffaroni sería verdadera, pero para mí no están bien. Abajo dejo las definiciones de Zaffaroni)
Arbol completo
Un árbol es completo cuando todos sus nodos no maximales tienen igual grado de salida.
(sería una definición igual a la de "Lleno" explicada arriba)
Arbol lleno
Un árbol es lleno cuando es un árbol completo y todos sus nodos maximales tienen igual profundidad.
(sería Similar a la de "Completo" explicada arriba, pero esta definición no acepta que haya hojas en distinto nivel, y sólo aceptaría como mínimo y máximo (2^h+1)-1 nodos, y no me parece que esté bien.)
Por lo que para no mezclar tomaría las definiciones del principio directamente.