domingo, 13 de fevereiro de 2011

115-2008

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"):








  1. NDA
Autor(a): Fabio L. Usberti

2 comentários:

  1. 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:

    Dada 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.

    ResponderExcluir
  2. 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