Questão FC871671
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 estru
Algoritmos e Lógica de Programação
FGV · 2026
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.
- A 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.
- As árvores rubro-negras representam uma particularização das árvores AVL e tries, preservando a característica do balanceamento do sucessor imediato entre subárvores.
- Dado 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).
- Em uma árvore rubro-negra T, se um nó v não raiz pertencente à T é rubro, então seu pai é negro.
- Em 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(n2).
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
A alternativa afirma que, em uma árvore rubro-negra, se um nó rubro v (não raiz) pertence à árvore, então seu pai é preto. Essa afirmação expressa uma das propriedades fundamentais: não existem dois nós rubros consecutivos na mesma raiz-para-folha.
Essa restrição evita cadeias longas formadas apenas por nós rubros, mantendo o equilíbrio. Em conjunto com a propriedade de que toda raiz-folha tem o mesmo número de nós pretos, a chamada altura preta \(bh\), resulta em um limite para a altura total da árvore: cada caminho tem no máximo \(2\cdot bh\) nós, porque entre dois nós pretos pode haver no máximo um nó rubro. Portanto, exigir que o pai de um nó rubro seja preto é crucial para garantir tempo logarítmico nas operações.
Conteúdo do catálogo FC Concursos · Atualizado em