Comentários
Questão 1
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.
Questão 2
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.
Questão 3
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
(
n
lg
n
)
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()
,...
Questão 4
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).
Questão 5
-
Deve ser árvore de busca: respeitar ordem.
-
Forçar balanceamento negro perfeito
Questão 8
BST
, RedBlackBST
, TrieST
e TST
são todas árvores de busca. BST
e RedBlackST
são binárias. TST
é ternária. TrieST
é R
-ária.
Questão 9
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.
Questão 10
Nem todo código livre de prefixo ótimo corresponde a uma trie gerada pelo algoritmo de Huffman.