wal

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O professor Astolfo, palmeirense fanático, decidiu criar uma árvore alviverde, com as seguintes propriedades:

1. Todo nó é verde ou branco;
2. A raiz é verde;
3. Toda folha (NIL) é verde;
4. Se um nó é branco, então ambos os seus filhos são verdes.
5. Para cada nó, todos os caminhos desde um nó até as folhas descendente contêm o mesmo número de nós verdes.

É correto afirmar que:

a. Todo nó verde na árvore alviverde equivale a todo nó vermelho na árvore vermelho-preto.
b. As operações feitas sobre uma árvore vermelho-preto são assintoticamente menores que as operações feitas sobre uma árvore alviverde.
c. A árvore alviverde e a árvore vermelho-preto se equivalem, sendo as cores dos nós a única diferença entre ambas, onde os nós verdes equivalem aos vermelhos, e os nós brancos equivalem aos nós pretos.
d. Um árvore vermelho-preto gerada, a partir de uma entrada de n chaves, é a mesma para uma árvore alviverde, sobre a mesma entrada.
e. NDA

Ideia Original: Wallace Felipe Francisco Cardoso