Ache a árvore PQ correspondente ao seguinte problema: U=abcde, S={abc, be, cd}. Mostre as árvores intermediárias obtidas adicionando um conjunto de cada vez.
SOLUÇÃO: Veja no texto do colega João Paulo.
Considere o conjunto universo U = {a1, a2, a3, ..., an} e a coleção S = {a1a2, a1a2a3, a1a2a3a4, ..., a1a2...an-2an-1}. Qual será a árvore PQ correspondente a este problema? Qual será a norma desta árvore? Ao adicionarmos o conjunto a1an a esta árvore, qual será o tamanho de PRUNED? Qual será a árvore resultante e qual sua norma?
SOLUÇÃO:
Árvore correspondente ao problema:
Norma: 2n-2. Este número foi obtido da seguinte forma: n folhas + n-2 nós internos cujo pai é do tipo P.
Tamanho de PRUNED para a1an: n arestas, e portanto n-1 nós.
Árvore resultante:
Norma da árvore resultante: 1
O algoritmo BUBBLE dado no artigo de Booth e Lueker só funciona quanto o conjunto S pode ser adicionado à árvore T gerando uma nova árvore não nula. Escreva um algoritmo eficiente que encontra a raiz da subárvore pertinente em qualquer caso. Suponha que todos os nós tenham apontador para o pai.
SOLUÇÃO: Veja algoritmo do colega Victor Iizuka. Ele pressupõe um passo anterior onde para cada nó pertinente é calculado o número de filhos pertinentes que o nó tem. Este passo é facilmente adaptável do algoritmo BUBBLE.