p6

Re: p6

por José Coelho de Pina -
Número de respostas: 0

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:

  1. links rubros se inclinam para a esquerda (left leaning. Outros autores não exigem isso. Essa forma canônica simplifica o código.);
  2. nenhum nó incide em dois links rubros;
  3. 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).