05-2011 - MO640 - Questão para prova oral

De acordo com o relatório técnico Construção incremental de árvores PQR, no algoritmo incremental, encontramos a função preparar_raiz(r). O que exatamente esta função faz dentro do algoritmo?

1. verifica se r é um nó do tipo P e, se for, transforma o nó P em nó Q;
2. verifica se r é um nó do tipo P e, se for, move os filhos para fora da raiz;
3. verifica se r é um nó do tipo P e, se for, une os filhos negros;
4. verifica se r é um nó do tipo P e, se for, reverte condicionalmente os nós cinza;
5. NDA.