a) Para construir a árvore T de prefixo mínima usando o algoritmo de Huffman, devemos seguir os seguintes passos: 1. Organizar as frequências dos símbolos em ordem crescente: B (1), D (1), C (2), A (5). 2. Juntar os dois símbolos de menor frequência em um único nó, criando uma subárvore. Repetir esse processo até que todos os símbolos estejam em uma única subárvore. 3. Atribuir o valor 0 para a aresta que leva ao símbolo de maior frequência em cada subárvore e o valor 1 para a aresta que leva ao símbolo de menor frequência. A árvore T de prefixo mínima obtida é a seguinte: ``` 9 / \ / \ 4 5 / \ / \ B D C A ``` b) A tabela de palavras-código construídas a partir da árvore T é a seguinte: | Símbolo | Frequência | Palavra-código | |---------|-----------|----------------| | A | 5 | 1 | | B | 1 | 00 | | C | 2 | 01 | | D | 1 | 001 | c) O custo C(T) da árvore obtida pelo algoritmo de Huffman é dado pela soma do produto entre a frequência de cada símbolo e o comprimento de sua palavra-código: C(T) = 5*1 + 1*2 + 2*2 + 1*3 = 14
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar