Número: 120
Enunciado:
No último passo do algoritmo quase-linear para adição de uma nova restrição a uma árvore PQR, quais são os nós que precisarão ser descoloridos?
- Todos os nós P pretos da árvore
- Todos os nós P cinzas da árvore
- Todos os nós pretos da árvore
- Todos os nós cinzas da árvore
- NDA
Antes de comentar cada alternativa, é importante ressaltar que deve-se mexer no mínimo de nós possíveis para não estourar a complexidade do algoritmo. Por esta razão, os nós brancos são considerados incolores e não são descoloridos.
ResponderExcluirO último passo do algoritmo limpa os estados dos nós mexidos na árvore, inclusive acima do LCA.
Sobre as alternativas ...
A alternativa "a" é incorreta, pois todos os nós pretos são descoloridos, independente se é P.
A alternativa "b" é incorreta, pois o terceiro passo do algoritmo já eliminou todos os nós cinzas.
A alternativa "c" é a CORRETA, porque no último passo, só restam nós pretos na árvore a serem descoloridos.
A alternativa "d" é incorreta, pois o terceiro passo do algoritmo já eliminou todos os nós cinzas.
A alternativa "e" é incorreta, já que a alternativa "c" já foi validada como correta.