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 e

Question

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.

Accepted Answer

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

Answer

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

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

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

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

Questão 13336 —

Comentários