Questão 2974928

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(n²).