Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADESP 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq333400
Banca
FADESP
Órgão
IF-PA
Ano
2018
Nível
Superior
Cargo
Professor - Informática
Sobre as árvores balanceadas do tipo vermelho-preto, é correto afirmar que
Ase um nó é filho da raiz da árvore, então ele é preto.
Bse um nó é preto, então pelo menos um dos seus filhos é vermelho.
Cse um nó é a raiz da árvore, então ele é vermelho.
Dse um nó é vermelho e não é a raiz da árvore, então seu pai é preto.
Eas alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade.
Revelar gabarito e comentário▾
GabaritoD — se um nó é vermelho e não é a raiz da árvore, então seu pai é preto.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Árvores Vermelho-Preto (Rubro-Negras)
Gabarito: letra D. Em árvores vermelho-preto, a propriedade fundamental é: "se um nó é vermelho, seus filhos são pretos". Isso implica que um nó vermelho (que não seja a raiz) tem pai preto, exatamente o que afirma a alternativa D. As demais alternativas violam as regras clássicas.
As cinco propriedades que definem uma árvore vermelho-preto são:
Todo nó é vermelho ou preto.
A raiz é preta.
Toda folha (NIL) é preta.
Se um nó é vermelho, ambos os seus filhos são pretos.
Para cada nó, todos os caminhos simples do nó até as folhas descendentes contêm o mesmo número de nós pretos.
Alternativa A — ❌ Incorreta
Afirma que "se um nó é filho da raiz, então ele é preto". A raiz é sempre preta (propriedade 2), mas seus filhos podem ser vermelhos ou pretos, desde que a propriedade 4 seja respeitada. Não há obrigatoriedade de serem pretos.
Alternativa B — ❌ Incorreta
Afirma que "se um nó é preto, então pelo menos um dos seus filhos é vermelho". Isso não é verdade: um nó preto pode ter ambos os filhos pretos, e a árvore ainda será válida (desde que a propriedade 5 seja mantida).
Alternativa C — ❌ Incorreta
Afirma que "se um nó é a raiz, então ele é vermelho". A propriedade 2 determina exatamente o contrário: a raiz deve ser preta.
Alternativa D — ✅ Correta ⟵ GABARITO
Afirma que "se um nó é vermelho e não é a raiz, então seu pai é preto". Isso decorre diretamente da propriedade 4: um nó vermelho não pode ter pai vermelho, portanto seu pai é preto. É a única alternativa que descreve corretamente uma propriedade invariante das árvores vermelho-preto.
Alternativa E — ❌ Incorreta
Afirma que "as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade". Essa é a definição de árvore AVL (balanceada por altura), não de árvore vermelho-preto. Em árvores vermelho-preto, o balanceamento é baseado na cor e na contagem de nós pretos, garantindo que a altura seja no máximo .
NÃO CAIA NESSA!
A banca troca o critério de balanceamento da árvore vermelho-preto pelo da árvore AVL (alternativa E). O candidato desatento confunde os dois tipos. Lembre-se: AVL exige diferença de altura máxima 1; vermelho-preto usa cores e garante que o caminho mais longo tem no máximo o dobro do mais curto.