Oi Daniel,
Entendo que a árvore do item (c) tem balanceamento perfeito, mas não considerei que essa árvore fosse uma BST rubro-negra justamente por não haver nós rubros nela.
Legal que você levantou essa questão.
Há duas meneira de vermos que (c) é uma ST rubro-negra. Na verdade, as duas são a mesma.
Perspectiva de árvore 2-3: uma ST rubro-negra é uma implementação de um ST 2-3.
A árvore em (c) é uma ST 2-3 em que todos os nós são 2-nós.
Logo ela é uma ST rubro-negra.
Perspectiva de árvore rubro-negra. A definição procura capturar a estrutura de uma árvore 2-3 em uma árvore binária.
Uma BST rubro-negra é uma BST cujos links são negros e rubros e:
- links rubros se inclinam para a esquerda (left leaning. Outros autores não exigem isso. Essa forma canônica simplifica o código.);
- nenhum nó incide em dois links rubros;
- balanceamento negro perfeito: todo caminho da raiz até um link
null
tem o mesmo número de links negros.
A BST (c) satisfaz (1) e (2) acima, já que não há links rubros (a ST 2-3 correspondente não tem 3-nós).