008-2011

MO640 - Questão para a prova oral

Enunciado:
Sobre uma das inovações do algoritmo apresentado em “Building PQR trees in almost-linear time”, publicado em 2005 por Telles e Meidanis, podemos afirmar que:

1. Substitui o processo de comparação de padrões das árvores PQ por um algoritmo mais simples, que depende apenas dos tipos de nós cinza e do LCA (Least Common Ancestor)
2. Separa o problema da construção das árvores PQR em duas partes distintas, representadas pelos algoritmos BUBBLE e REDUCE.
3. Faz uma adaptação da técnica de divisão e conquista para dividir a árvore inicial em subárvores menores
4. Utiliza um algoritmo de hash para reduzir a quantidade de informações relacionadas aos nós brancos
5. NDA

Ideia original de: Adriano Batista Prieto