Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CIAAR 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
gp019091
Banca
CIAAR
Órgão
CIAAR
Ano
2026
Cargo
Oficial de Apoio - Análise de Sistemas
Observe as assertivas abaixo e, em seguida, assinale a alternativa correta.I. Uma árvore rubro-negra com n nós internos tem altura no máximo2 lg (n + 1).PORQUEII. As propriedades das árvores rubro-negras garantem que nenhum caminho da raiz até uma folha seja mais do que duas vezes mais longo que qualquer outro caminho, mantendo a árvore aproximadamente balanceada.
AAs duas são verdadeiras, e a II justifica a I.
BAs duas são verdadeiras, mas a II não justifica a I.
CI é verdadeira, e II é falsa.
DI é falsa, e II é verdadeira.
Revelar gabarito e comentário▾
GabaritoA — As duas são verdadeiras, e a II justifica a I.
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 Rubro-Negras
Gabarito: letra A. Ambas as assertivas são verdadeiras e a segunda (II) justifica a primeira (I), conforme as propriedades clássicas das árvores rubro-negras. A assertiva I expressa o limite superior da altura (2 lg (n+1)), que é uma consequência direta da propriedade descrita em II: nenhum caminho da raiz até uma folha é mais que o dobro de qualquer outro caminho, garantindo o balanceamento aproximado.
A demonstração de que a altura máxima é O(log n) usa exatamente essa propriedade: o caminho mais longo (com alternância de cores) tem no máximo o dobro do número de nós pretos do caminho mais curto (todo preto), o que limita a altura total. Portanto, II fornece a justificativa para I.
Alternativa A — ✅ Correta ⟵ GABARITO
Ambas as assertivas são verdadeiras e a II justifica a I. A altura máxima de uma árvore rubro-negra com n nós internos é de fato 2 lg (n+1), como demonstrado na literatura (Cormen et al.). A propriedade do balanceamento (caminho máximo ≤ 2× caminho mínimo) é a base para essa prova.
Alternativa B — ❌ Incorreta
Afirma que II não justifica I. Na verdade, a propriedade do dobro do comprimento é essencial para derivar o limite de altura. Sem ela, não seria possível garantir a cota logarítmica. Portanto, a justificativa existe.
Alternativa C — ❌ Incorreta
Diz que I é verdadeira e II é falsa. II é verdadeira: as propriedades rubro-negras (raiz preta, folhas pretas, filhos de vermelho são pretos, mesmo número de pretos por caminho) implicam que o caminho mais longo (alternando cores) é no máximo duas vezes o mais curto (todo preto). Portanto, a árvore é aproximadamente balanceada.
Alternativa D — ❌ Incorreta
Diz que I é falsa e II é verdadeira. I é verdadeira: a altura máxima de uma rubro-negra com n nós internos é 2 lg (n+1). Esse é um resultado clássico e pode ser provado por indução ou pela relação entre número de nós e altura.
PEGA ESSA DICA!
Para questões sobre árvores rubro-negras, lembre-se sempre das propriedades: (1) cada nó é vermelho ou preto; (2) raiz é preta; (3) folhas (NIL) são pretas; (4) filhos de nó vermelho são pretos; (5) todos os caminhos da raiz até as folhas têm o mesmo número de nós pretos. Essas propriedades garantem o balanceamento e a altura O(log n).