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.
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?
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. Contudo, em classe foi visto um algoritmo que encontra a raiz da subárvore pertinente em qualquer caso. Escreva este algoritmo em pseudo-código.
© 2007 João Meidanis