QUESTIONÁRIO 04 - ÁRVORES AVL (BALANCEADAS)

1)         Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL?

Resposta: Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós. O Fator de Balanceamento (FB) é utilizado pela seguinte fórmula:

FB(nó) = altura(dir)  - altura(esq)

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

2)         Sabendo que podemos inserir elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de inserção na árvore AVL e do seu algoritmo.

Resposta: Primeiro, c é inserido como folha A, seguindo o algoritimo do caso geral das ABBs. Se depois da inserção a árvore permanece AVL, então nada mais temos a fazer. Caso contrário, é necessário remanejar a árvore.

3)         Sabendo-se que os conceitos de rotação simples a direita/esquerda e de rotação dupla a direita/esquerda são essenciais na inserção de elementos na árvore avl. Explique os conceitos de rotação simples e rotação dupla.
Resposta: Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".

4)         Sabendo que podemos retirar elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de remoção na árvore AVL e do seu algoritmo.
Resposta: A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.

1. Remover X da árvore AVL usando o mesmo algoritmo de remoção de um nó em uma árvore de busca binária. Recursivamente, empilhar cada nó que é visitado a partir do nó raiz até o nó X, incluindo-o;
2. Verificar se a pilha está vazia
• Se sim, o algoritmo termina.
• Senão, vá para o passo (3).
3. Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da esquerda e da direita desse nó é maior que 1.
• Se sim, você precisará rotacionar os nós. Dependendo do tipo de rotação realizada, o algoritmo pode não terminar aqui. Se ele não terminar, vá para o passo (2).
• Senão, vá para o passo (2). 

Note que a operação de remoção pode ser realizada em tempo O(lg(n)). Na remoção de um elemento em uma árvore AVL, pode haver a necessidade de realizar mais de duas rotações (o que não acontece na inserção), podendo se estender para uma rotação em cada nível (O(log(n))) no pior caso. A figura a seguir mostra um exemplo deste caso:

5)         Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.

Resposta: Exemplo de remoção:                                                                                                            Exemplo 1 : Dada a árvore abaixo, retirando o 5 resulta uma arvore desbalanceada no nó 10(b). A partir daí, raciona-se como se estivéssemos inserindo: que nó inserido teria causado esse desequilíbrio? O 30. Aplicando os conhecimentos de inserção em arvore AVL, constata-se que uma rotação simples a esquerda resolve o problema. O resultado esta na AVL(C).

 

Exemplo 2: Retirando a folha 12 de (a), na figura abaixo, desbalanceia a raiz (b); supondo-se a inserção recente de 8, corrige-se o desequilíbrio mediante uma rotação dupla a esquerda (c).

Exemplo de inserção:

Exemplo 1: Inserção seqüencial ( Chaves de 1 a 7) em arvore AVL em destaque nós P e U dos exemplos que precisam de rotação ( e Y, filho que precisa “Trocar de Pai) em vermelho), nos retângulos arvore antes e após a rotação:

 

Exemplo 2:

Inserção das Chaves 80,40,60,50 e 45 (nessa seqüência ):