Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fg131896
Banca
FGV
Órgão
PC-PI
Ano
2026
Nível
Superior
Cargo
Perito Criminal - Informática Forense
A árvore rubro-negra é uma estrutura de dados de árvore auto-balanceada que mantém propriedades específicas para garantir desempenho consistente na manipulação de dados. Essa estrutura está presente em diversos componentes utilizados, por exemplo, em ferramentas de computação forense, como indexadores, analisadores de sistemas de arquivos e mecanismos de ordenação de eventos.No que concerne a árvores rubro-negras, assinale a opção correta.
AA altura negra (black-height), definida como o número de nós negros no caminho da raiz até qualquer descendente nó externo, pode variar, desde que a árvore mantenha a propriedade de nenhum nó vermelho possuir filhos vermelhos.
BAs árvores rubro-negras representam uma particularização das árvores AVL e tries, preservando a característica do balanceamento do sucessor imediato entre subárvores.
CDado que uma operação de inclusão pode desequilibrar uma árvore rubro-negra, as operações de equilíbrio para restabelecer as condições da estrutura são efetuadas com complexidade de tempo igual a O(n).
DEm uma árvore rubro-negra T, se um nó v não raiz pertencente à T é rubro, então seu pai é negro.
EEm uma remoção, o nó excluído deve ser substituído pelo nó cuja chave é o menor valor disponível no sub-ramo direito da árvore, com tempo O(n² ).
Revelar gabarito e comentário▾
GabaritoD — Em uma árvore rubro-negra T, se um nó v não raiz pertencente à T é rubro, então seu pai é negro.
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 D. Em uma árvore rubro-negra, uma das propriedades fundamentais é que todo nó vermelho (exceto a raiz) deve ter pai preto. Essa condição evita dois nós vermelhos consecutivos e é essencial para o balanceamento. As demais alternativas apresentam erros conceituais ou de complexidade.
Propriedade / Característica
Descrição Correta
Descrição Incorreta (Alternativa)
Altura negra (black-height)
Número de nós negros da raiz até qualquer folha; deve ser igual em todos os caminhos.
Pode variar, desde que nenhum nó vermelho tenha filho vermelho (Alternativa A).
Relação com outras estruturas
Árvore rubro-negra é um tipo independente de árvore balanceada.
É uma particularização de árvores AVL e tries (Alternativa B).
Complexidade do reequilíbrio
O(log n) após inserção ou remoção.
O(n) (Alternativa C).
Cor do pai de um nó vermelho (não raiz)
Preto (propriedade fundamental).
— (Alternativa D é a correta).
Remoção: substituição e complexidade
Substituição pelo sucessor (menor nó da subárvore direita) ou predecessor; complexidade O(log n).
Substituição pelo menor valor do sub-ramo direito; complexidade O(n²) (Alternativa E).
Árvore rubro-negra: Propriedades (Raiz é preta, Nó vermelho → pai preto, Folhas (NIL) são pretas, Altura negra igual em todos os caminhos); Operações (Inserção: O(log n), Remoção: O(log n), Reequilíbrio: O(log n)); Relação com outras (Não é AVL, Não é trie)
Alternativa A — ❌ Incorreta
A altura negra (black-height) é definida como o número de nós negros no caminho da raiz até qualquer nó folha, e essa quantidade deve ser a mesma para todos os caminhos (propriedade 5 das árvores rubro-negras). A alternativa afirma que pode variar, o que contraria a definição.
Alternativa B — ❌ Incorreta
Árvores rubro-negras são um tipo independente de árvore balanceada, não uma particularização de árvores AVL ou tries. AVLs usam fator de balanceamento baseado em altura; tries são estruturas para strings. Não há relação de herança ou especialização.
Alternativa C — ❌ Incorreta
As operações de reequilíbrio após inserção ou remoção em árvores rubro-negras têm complexidade O(log n), conforme demonstrado no estudo clássico (Cormen et al., Algoritmos). O contexto fornecido explicitamente afirma que tanto inserção quanto eliminação são realizadas em tempo O(log n) (no máximo duas rotações na inserção e três na remoção). A alternativa alega O(n), o que é falso.
Alternativa D — ✅ Correta ⟵ GABARITO
A propriedade 4 das árvores rubro-negras estabelece que, se um nó é vermelho, seus dois filhos devem ser pretos. Consequentemente, um nó vermelho não pode ter pai vermelho, pois o pai vermelho teria um filho vermelho, violando a regra. Assim, em uma árvore válida, todo nó vermelho (não raiz) tem pai preto. A alternativa reproduz corretamente essa condição.
Alternativa E — ❌ Incorreta
Na remoção, quando o nó a ser excluído possui dois filhos, ele é substituído por seu sucessor (que é o menor nó da subárvore direita) ou predecessor, conforme a implementação. A complexidade das operações de remoção e reequilíbrio é O(log n), e não O(n²). A alternativa erra tanto na descrição do sucessor (não é necessariamente o "menor valor disponível no sub-ramo direito" — essa é apenas uma das opções) quanto na complexidade.