Sobre as árvores balanceadas do tipo vermelho-preto, é corre...

Próximas questões
Com base no mesmo assunto
Q946467 Algoritmos e Estrutura de Dados
Sobre as árvores balanceadas do tipo vermelho-preto, é correto afirmar que
Alternativas

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