Question

PÁGINA 12

A árvore rubro-negra é uma estrutura de dados de árvore autobalanceada 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.

Accepted Answer

D) Em uma árvore rubro-negra T, se um nó v não raiz pertencente à T é rubro, então seu pai é negro.

Answer

A) 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.

Answer

B) 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.

Answer

C) 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).

Answer

E) 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).

Mais questões de Árvores e grafos