Comentários?
Solução [pdf].
Professor, no caso da árvore rubro negra (b), porque ela não tem balanceamento perfeito rubro negro? (supondo que o node maior no lado esquerdo da árvore fosse um menor que a raiz)
a árvore b não te balanceamento negro perfeito pq se vc olhar as folhas 7 e 32 tem distância negra pra raiz igual a 1, e as folhas 39 e 49 tem distância negra igual a 2.
Gabriel, muito obrigado por compartilhar a dúvida!
Guilherme, muito obrigado pela colaboração!
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.
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
nulltem 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).