MO640 - Questão para a prova oral
Número: 115
| Enunciado:
Considere a sub-árvore PQR à esquerda, com os nós coloridos em preto, cinza e branco da maneira descrita no artigo Building PQR Trees in Almost-Linear Time (Telles & Meidanis, 2007). Seja o nó r o mínimo ancestral comum (LCA - least common ancestor) e seja o nó v um nó cinza que se deseja eliminar. Verifique qual das sub-árvores abaixo melhor representa o processo "transformar nó P em nó Q" ("transform P node into Q node"): |
- NDA
Autor(a): Fabio L. Usberti
No passo três, sabemos que a transformação dos nós P's da cor cinza se transformam em nós Q's. O algoritmo está melhor detalhado na seção 3.2 do documento Construção Incremental de árvores PQR, página 9, como segue:
ResponderExcluirDada a árvore do exercício em questão, primeiramente devemos criar um nó Q cinza que vamos chamar de g e deve ser filho de r, depois de v.
1.Se v tem dois ou mais filhos negros, então é criado um nó P que vamos chamar de b, de cor negra, e cada filho negro de v é movido para dentro de b(estamos unindo os nós pertinentes ou da restrição em b); se v tiver apenas um filho, move-o para g;
2.Move-se todos os filhos cinza de v para g (sem criar nós);
3.Se v ainda tem dois ou mais filhos, então são brancos e o nó v é movido para g e pintado de branco; se v tiver um único filho ele é branco; então move-se este último para g; e o nó v é destruído.
Fica claro pelo algoritmo que, dado o problema da árvore, será criado um nó Q e em seguinda um nó P negro onde receberá os filhos de p1 a px que são negros. Em seguida, todos os filhos cinza, c1 à cx serão movidos para o nó v e, por último, o nó v que contém os filhos brancos, b1 à bx, será pintado de branco e transferido para o nó Q, terminando assim a etapa “transformar nó P em nó Q” do algoritmo, nos mostrando que a resposta correta é a alternativa a.
Bom comentário, Alex. Só note que, no seu parágrafo final, os nós cinzas vão para o novo nó Q, e não para v.
ResponderExcluir