Comentários?
Solução [pdf].
Boa tarde, professor.
Na verdade, acho que não entendi a questão 1. Eu fiz o desenho da árvore e ela ficou assim:
0
| \ \ \
1 2 3 4
| \ \
567
|
8
|
9
Esse modelo não é adequado por que cada pai tem apenas dois filhos (um esquerdo e um direito) em uma weighted quick union?
A resposta que eu dei foi diferente. Eu considerei que se id[1] = 0, então id[5] não poderia ser 1, seria 0 também (como se 0 fosse o pai de todos).
Obrigada!
Oi Bruna,
Na verdade, acho que não entendi a questão 1. Eu fiz o desenho da árvore e ela ficou assim:
Legal que você perguntou!
Na estrutura de dados disjoint set forest usada para representar conjuntos disjunto dinâmicos sob as operações de union() e find() cada nó da árvores tem uma referências para o seu pai. Assim, um nó pode ter vários flhos como você desenhou.
Veja, por exemplo, os exemplos nos slides da aula03.