Salve,
Antes que a coisa esfrie, coloquei um cópia da prova 2 e de uma solução aqui.
Corrigi os erros na prova que o Cesar (private boolean color; na questao 1) e o Caio (18->20 na questão 5) me avisaram durante a prova.
Se encontrarem algo errado na prova ou na solução, por favor, avisem.
Críticas, sugestões e comentários são sempre bem-vindos.
Professor, fiquei com duas dúvidas:
Na questão 5. (a), o 21 não poderia ser também a chave '??' ?
Na questão 10. (c), no código 4, o 11 não é um prefixo?
Oi Rodrigo,
Na questão 5. (a), o 21 não poderia ser também a chave '??' ?
Você tem razão.
Na questão 10. (c), no código 4, o 11 não é um prefixo?
Novamente, você tem razão.
Já corrigi esses erros.
Muito obrigado!
Variáveis de referência Node, Key, Value gastam tipcamente 8 bytes.
Há uma gasto extra com padding, memória alocada é tipicamente um multiplo de 8 bytes.
Mensagem: é sua responsabilidade como programador em saber, pelo menos aproximadamente, se o espaço requerido pelo seu programa vai impedir que seu problema seja resolvido.
Overhead com um objeto é tipicamente de 16 bytes. Isso inclue referência para a classe do objeto e informação para o coletor de lixo.
Mensagem: é muito bacana podermos codificar a estrutura de uma árvore binária em que cada nó interno tem dois filhos/filhas em uma sequêcia de bits. A implementação de Huffman usa essa representação para armazenar a TST dos códigos.
O consumo de tempo para construirmos uma árvore com n nós é pelo menos proporcional a n.
A recursão tem uma estrutura muito parecida a do mergesort(). Como o consumo de tempo de cada chamada recursiva é constante, então o consumo de tempo total é O(n).
O consumo de tempo do mergesort() é O(nlgn) pois em cada chamada recursiva o consumo de tempo é determinado pelo tempo da intercalação de dois vetores (=merge()).
A posição do meio de um vetor keys[ini..fim] é (ini+fim)/2 == ini + (fim-ini)/2.
Em chamadas recursivamos em que passamos um intervaor ini..fim devemos ser consistentes sobre o fato do intervalo ser aberto/fechado à esquerda/direita.
Mensagem: estrutura clássica de recursão, tipo divisão e conquista: mergesort(), quicksort(),...
A árvore não é única. Devemos ser consistentes em relação as subárvores à esquerda e direita: subárvore esquerda cresce/diminui a coordenada x (ou y); subárvore direita cresce/diminui a coordenada x (ou y).
Deve ser árvore de busca: respeitar ordem.
Forçar balanceamento negro perfeito
BST, RedBlackBST, TrieST e TST são todas árvores de busca. BST e RedBlackST são binárias. TST é ternária. TrieST é R-ária.
Prestar atenção em relação aos possíveis valores de ? de tal forma que a TST respeita a condição de ser uma árvore de busca.
Nem todo código livre de prefixo ótimo corresponde a uma trie gerada pelo algoritmo de Huffman.