Figura 1: Um exemplo de árvore PQ.

O artigo define sub-árvore pertinente em relação ao conjunto S como sendo a sub-árvore de menor altura cuja fronteira contém todos os elementos de S. é bom lembrar que o artigo utiliza dois conceitos de sub-árvore distintos. No caso da sub-árvore pertinente, todos os vértices abaixo da raiz da sub-árvore na árvore PQ original também estão na sub-árvore. A Figura 2 mostra um exemplo de sub-árvore pertinente para a árvore da Figura 1.

Note que, apesar de o tamanho de uma árvore PQ ser linear no tamanho do conjunto universo U, não é possível dizer que o tamanho da sub-árvore pertinente é linear ao tamanho do conjunto S. Por exemplo, é possível determinar um conjunto S com apenas dois elementos tal que o ancestral comum mais baixo entre os elementos seja a raiz da árvore PQ, como o caso de S={A, K}, considerando a árvore da Figura 1. Neste caso, a sub-árvore pertinente é a própria árvore PQ.

Em aula, vimos que é possível criar um conjunto S de cardinalidade 2 tal que o ancestral comum mais baixo entre os elementos de S seja a raiz da árvore PQ qualquer que seja o conjunto universo e qualquer que seja a árvore PQ, bastando para isso pegar um dos filhos da raiz como um dos dois elementos de S.

Figura 2: Sub-árvore pertinente para a árvore PQ na Figura 1 quando S={E, I, J, K}.

A sub-árvore pruned-pertinente de uma árvore PQ em relação ao conjunto S é definida como o menor subgrafo conexo que contém todas as folhas pertinentes, ou seja, todas as folhas que pertencem a S. Note que a sub-árvore pruned-pertinente não é necessariamente uma árvore PQ.

Lembrando novamente que o artigo usa duas definições distintas de sub-árvore. Aqui sub-árvore é um sub-grafo conexo da árvore. Nem todos os vértices abaixo da raiz da sub-árvore na árvore PQ original precisam fazer parte da sub-árvore neste caso.

Figura 3: Sub-árvore pruned-pertinente para a árvore PQ na Figura 1 quando S={E, I, J, K}.

Sugerimos uma estrutura de dados para armazenar árvores PQ e tentamos sugerir alguns algoritmos que, assim como o sugerido no artigo, marcasse os elementos de uma sub-árvore pruned-pertinente em tempo proporcional ao tamanho da sub-árvore.

A Figura 4 mostra a árvore PQ da Figura 1 representada pela estrutura de dados desenvolvida em aula. Nela, tanto nós P quanto nós Q quanto as folhas da árvore são representados por um mesmo tipo, representado no canto inferior esquerdo da figura. O campo Tipo contém o valor P para nós do tipo P, o valor Q para nós do tipo Q e o identificador da folha, no caso de representar uma folha. Os apontadores para os pais dos nós ajudam a subir na estrutura para determinar o ancestral comum mais baixo de um conjunto de folhas. Além disso, o vetor presente na base da figura permite acesso direto às folhas da árvore, facilitando a identificação das folhas que pertencem ao conjunto S.

Figura 4: Árvore PQ da Figura 1 representada pela estrutura de dados desenvolvida em aula. No canto inferior esquerdo há um exemplo de um dos nós da árvore. O campo Tipo indica o tipo do nó, o campo #F. contém o número de filhos do nó, o campo M uma marca, o campo Filhos a lista de filhos do nó e o campo Pai um apontador para o pai do nó. Abaixo encontra-se um vetor que facilita o acesso às folhas.

Duas estratégias foram sugeridas em aula para resolver o problema de achar o ancestral comum mais baixo de um conjunto de 2 folhas de uma árvore PQ.

Sugestão 1

Usar as distâncias dos nós à raiz para determinar o ancestral comum mais baixo. A marca no tipo que representa um nó da árvore seria usada para armazenar a distância do nó até a raiz. É possível então determinar o nó que está à distância maior da raiz e subir, usando os apontadores para os pais, até chegar a um nó que está à mesma distância da raiz que o outro nó. A partir daí, basta continuar subindo pela árvore de maneira sincronizada até encontrar um nó comum.

Problema: Atualizar as distâncias pode ser extremamente custoso. Para cada novo nó inserido é preciso atualizar todos seus descendentes, passando inclusive por nós que não precisariam ser levados em conta. O algoritmo do artigo consegue achar o ancestral comum mais baixo em O(PRUNED(T,S)), o que é linearmente proporcional ao tamanho sub-árvore pruned-persistente da árvore T em relação ao conjunto S.

Sugestão 2

Subir com um nó de cada vez. Escolher um dos nós e subir até a raiz, marcando os nós encontrados no caminho. Quando chegar à raiz, pegar o outro nó e repetir o procedimento até encontrar um nó já marcado. O nó já marcado encontrado é o ancestral comum mais baixo.

Problema: Sempre é preciso subir até a raiz, mesmo quando se trata de duas folhas irmãs. No caso de duas folhas irmãs, por mais que a segunda subida seja rápida, a primeira já pode ser maior que o tamanho da sub-árvore pruned-pertinente.

Não chegamos a um consenso a respeito de como o algoritmo do artigo funciona, mas Meidanis mandou um email para a lista e eu tentarei explicar o que eu entendi.

O algoritmo funciona em duas partes: uma em que os nós da sub-árvore pruned-pertinente ficam sabendo quantos filhos pertinentes eles têm e outro em que o ancestral comum é determinado.

Calculando o número de filhos

1. Todas as folhas em S são postas numa fila.
2. Tira o nó n da fila.
3. Incrementa o contador de filhos do pai de n.
4. Se o pai de n não estiver na fila, inserí-lo.
5. Repetir a partir do passo 2 até que a fila tenha apenas um elemento.

Note que todos os nós da sub-árvore pruned-pertinente são visitados apenas uma vez. O procedimento pode fazer com que alguns nós acima da raiz da sub-árvore sejam visitados, mas estes nós não são visitados na segunda parte do algoritmo e não são em número suficiente para fazer a complexidade do algoritmo ir além de algo linearmente proporcional ao tamanho da sub-árvore pruned-pertinente.

Encontrando o ancestral comum mais baixo

1. Todas as folhas em S são postas numa fila.
2. Tira o nó n da fila.
3. Incrementa o contador de filhos visitados do pai de n.
4. Se a fila estiver vazia, retorne o pai de n como ancestral comum mais baixo. (o algoritmo para aqui!)
5. Se o contador de filhos visitados do pai de n for igual ao número de filhos, coloque-o na fila.
6. Repita a partir de 2.

Note que os contadores atualizados na primeira e na segunda parte são diferentes. Na segunda parte o contador de filhos não se altera, apenas o contador de filhos já visitados.

Note também que, como todos os caminhos das folhas em S até a raiz da árvore PQ passam pela raiz da sub-árvore pruned-pertinente em relação a S, nenhum caminho ultrapassa o ancestral comum mais baixo enquanto seu contador de filhos visitados for diferente do seu número de filhos na sub-árvore pruned-pertinente, mas essa condição é satisfeita exatamente na iteração em que a fila fica vazia e a raiz da sub-árvore é retornada como ancestral comum mais baixo.