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.
B As árvores rubro-negras representam uma particularização das árvores AVL etries, preservando a característica do balanceamento do sucessor imediato entre subárvores.
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).
D Em uma árvore rubro-negra T, se um nó v não raiz pertencente à T é rubro, então seu pai é negro.
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).