MO417 - Questão para a prova oral

Número: 046

Enunciado:
Uma árvore do tipo vermelho-preto deve satisfazer, entre outras, as propriedades:

1. A raiz é preta.
2. Se um nó é vermelho, então seus dois filhos são pretos.
3. Para cada nó, todos os caminhos desde um nó até as folhas descendentes contêm o mesmo número de nós pretos.

Para a seguinte árvore vermelho-preto, quais das propriedades 1, 2 e 3 continuam válidas após a execução de uma rotação à direita no nó de chave 25 seguida de uma rotação à esquerda no nó de chave 15?

1. Apenas 1.
2. Apenas 2.
3. Apenas 1 e 3.
4. 1, 2 e 3.
5. NDA.

Autor(a): Rodrigo Tripodi Calumby