Número: 119
Enunciado:
No artigo "Building PQR Trees in Almost Linear Time", de Telles e Meidanis, temos a descrição de um algoritmo para adicinar uma restricao S a uma arvore PQR T em cinco passos. O segundo passo se refere a coloração dos nós internos de T e a determinacao do ancestral comum mais recente das folhas de S. Sobre essa coloração, considere as afirmações a seguir:
I - Um nó é colorido com "cinza" quando sua intersecção com S é nula.
II - Um nó é colorido com "preto" se for ortogonal ao conjunto S.
III - Se o conjunto S estiver contido em um nó, então o nó deverá ser colorido com "branco".
Quais delas estão corretas?
- I
- III
- II, III
- I, II
- NDA
Para iniciar, lembre-se que dizemos que dois conjuntos A e B são ortogonais se A está contido em B, B está contido em A ou a união de A e B é vazia. Sendo assim:
ResponderExcluirI – FALSO: um nó é colorido com cor “cinza” quando ele não é ortogonal à restrição S.
II – FALSO: um nó é colorido com cor “preta” se todos os seus filhos estão contidos na restrição S.
III – VERDADEIRO: o nó interno que possui todos os elementos da restrição S deve ser pintado como “branco” e ele será o LCA (last common ancestor).
Posto isto, a resposta correta é a letra b).
Caro Michel,
ResponderExcluirMais atenção! Você cometeu 3 erros:
(1) na sua definição de ortogonalidade, falou "união" quando o certo é "intersecção".
(2) no seu comentário da II, a justificativa está incorreta. Preto é aquele nó que está proŕiamente contido em S. O que você falou pode não se verificar. Por exemplo: quando a LCA tem todos os filhos contidos em S, ela mesmo assim é branca.
(3) no seu comentário da III, você parece pensar que haverá apenas um nó que contém todos os elementos de S. Isto pode não ser verdade. Se o LCA não é a raiz da árvore toda, todos os ancestrais do LCA têm esta propriedade.