![]() |
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.
![]() | ||
|
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.Sugestão 2Problema: 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.
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
- Todas as folhas em S são postas numa fila.
- Tira o nó n da fila.
- Incrementa o contador de filhos do pai de n.
- Se o pai de n não estiver na fila, inserí-lo.
- 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
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.
- Todas as folhas em S são postas numa fila.
- Tira o nó n da fila.
- Incrementa o contador de filhos visitados do pai de n.
- Se a fila estiver vazia, retorne o pai de n como ancestral comum mais baixo. (o algoritmo para aqui!)
- Se o contador de filhos visitados do pai de n for igual ao número de filhos, coloque-o na fila.
- Repita a partir de 2.
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.