Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADESP 2024
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg129063
Banca
FADESP
Órgão
Prefeitura de Capanema - PA
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas
Em uma árvore binária de busca do tipo rubro-negra,
Ase um nó é vermelho, o filho da direita é preto e o da esquerda é vermelho.
Ba raiz sempre é vermelha e os nós folha (NIL) sempre são pretos.
Ca raiz sempre é preta, e se um nó é vermelho, ambos os filhos são pretos.
Dse um nó é vermelho, o filho da direita é vermelho e o da esquerda é preto.
Revelar gabarito e comentário▾
GabaritoC — a raiz sempre é preta, e se um nó é vermelho, ambos os filhos são pretos.
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”.
Árvore Rubro-Negra: Propriedades Fundamentais
Gabarito: letra C. Em uma árvore rubro-negra, a raiz é sempre preta e, se um nó é vermelho, ambos os seus filhos são pretos. Essa é a propriedade que define a coloração e garante o balanceamento aproximado.
A banca testa o conhecimento das regras de coloração de uma árvore rubro-negra, estrutura de dados balanceada derivada da árvore binária de busca. As propriedades clássicas são:
Cada nó é vermelho ou preto.
A raiz é preta.
Toda folha (NIL) é preta.
Se um nó é vermelho, então seus filhos são pretos.
Para cada nó, todos os caminhos simples descendentes até as folhas contêm o mesmo número de nós pretos.
Alternativa A — ❌ Incorreta
Afirma que, se um nó é vermelho, o filho da direita é preto e o da esquerda é vermelho. Fere a propriedade essencial: ambos os filhos de um nó vermelho devem ser pretos. A alternativa troca a cor do filho esquerdo, criando uma sequência vermelho-vermelho proibida.
Alternativa B — ❌ Incorreta
Diz que a raiz sempre é vermelha e os nós folha (NIL) sempre são pretos. Erro duplo: a raiz deve ser preta, não vermelha. As folhas NIL são de fato pretas, mas o erro na raiz invalida a alternativa.
Alternativa C — ✅ Correta ⟵ GABARITO
Afirma corretamente que a raiz é sempre preta e que, sendo um nó vermelho, ambos os filhos são pretos. Essas duas regras são pilares da árvore rubro-negra, garantindo que nenhum caminho tenha dois nós vermelhos consecutivos e que a árvore se mantenha balanceada.
Alternativa D — ❌ Incorreta
Inverte as cores: o filho da direita seria vermelho e o da esquerda preto. Novamente, a regra manda que ambos os filhos sejam pretos quando o pai é vermelho, independentemente de lado.
PEGA ESSA DICA!
Para não se confundir, memorize o mantra: "Raiz preta, folhas pretas, vermelho só com filhos pretos." E lembre-se: a raiz nunca é vermelha! Teste mental: se a raiz fosse vermelha, ela não teria pai para "quebrar a sequência", e as propriedades de balanceamento não se sustentariam.