Por que o pai de um nó rubro em uma árvore rubro-negra deve ser preto?

Resposta

O pai de um nó rubro deve ser preto para impedir a ocorrência de dois nós rubros consecutivos ao longo de um caminho.

Essa restrição evita cadeias longas formadas apenas por nós rubros e, junto com a propriedade de que toda raiz-folha tem o mesmo número de nós pretos (altura preta, bh), garante que cada caminho tenha no máximo \(2\cdot bh\) nós, mantendo altura logarítmica nas operações.