Sobre as árvores balanceadas do tipo vermelho-preto, é corre...
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
A alternativa correta é a alternativa D. Vamos entender o porquê desta ser a resposta correta e analisar também as alternativas incorretas.
Alternativa D: "Se um nó é vermelho e não é a raiz da árvore, então seu pai é preto."
Esta é a resposta correta. Em uma árvore vermelho-preto, uma das regras fundamentais é que um nó vermelho deve ter um pai preto. Isso é conhecido como a propriedade de não ter dois nós vermelhos consecutivos, o que ajuda a manter o balanceamento da árvore.
Por que as outras alternativas estão incorretas?
Alternativa A: "Se um nó é filho da raiz da árvore, então ele é preto."
Esta afirmação está incorreta. Na verdade, o filho da raiz pode ser vermelho ou preto. A única exigência é que a raiz da árvore seja sempre preta, mas nenhuma regra específica dita a cor dos seus filhos.
Alternativa B: "Se um nó é preto, então pelo menos um dos seus filhos é vermelho."
Esta afirmação também está incorreta. Um nó preto pode ter dois filhos pretos, dois filhos vermelhos ou um de cada cor. O importante é que todos os caminhos da raiz para as folhas tenham o mesmo número de nós pretos, garantindo que a árvore permaneça balanceada.
Alternativa C: "Se um nó é a raiz da árvore, então ele é vermelho."
Esta afirmação está errada. A raiz de uma árvore vermelho-preto deve ser sempre preta, conforme uma das regras fundamentais dessas árvores.
Alternativa E: "As alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade."
Esta afirmação descreve uma propriedade de árvores AVL e não de árvores vermelho-preto. Em uma árvore vermelho-preto, o balanceamento é menos rigoroso; permite-se que as alturas das subárvores diferem mais, mas ainda mantém o balanceamento global da árvore através das propriedades de cores e caminhos pretos.
Espero que esta explicação tenha esclarecido por que a alternativa D é a correta e ajudado a compreender as propriedades das árvores vermelho-preto. Se precisar de mais alguma coisa, estou à disposição para ajudar!
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
Algumas propriedades da Árvore red black:
*Um nó é vermelho ou preto.
*A raiz é preta. (Esta regra é usada em algumas definições. Como a raiz pode sempre ser alterada de vermelho para preto, mas não sendo válido o oposto, esta regra tem pouco efeito na análise.)
*Todas as folhas(nil) são pretas.
*Ambos os filhos de todos os nós vermelhos são pretos.
*Todo caminho de um dado nó para qualquer de seus nós folhas descendentes contem o mesmo número de nós pretos.
https://www.slideshare.net/KholtarRasklof/rvores-rubro-negras
1. Todo nó é vermelho ou preto
2. A raiz é preta
3. Toda folha (Nil) é preta
4. Se um nó é vermelho, então os seus filhos são pretos
5. Para cada nó, todos os caminhos do nó para folhas
descendentes contém o mesmo número de nós PRETOS.
Quanto à raiz: Ser sempre preta é uma regra usada em
algumas definições. Como a raiz pode sempre ser
alterada de vermelho para preto, mas não sendo válido o
oposto, esta regra tem pouco efeito na análise.
Resposta letra D
Força Guerreiro!!!!!!
Bizu
Lembrar de cabelo.
Que tem a raiz preta.
Pra não confundir com o vermelho!
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo