QUESTIONÁRIO 04 - ED II

QUESTIONÁRIO 04 - ÁRVORES AVL

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 raiz. 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 é uma árvore balanceada cuja diferença em altura entre a sub-árvore

esquerda e a sub-árvore direita (em qualquer nó) deve ser, no máximo, de um nível.

Numa árvore AVL, cada chave é única e as operações de inserção/ remoção tentam manter o equilíbrıo da árvore.

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:

Inserção: Inserção em uma árvore AVL deve ser dada pela inserção do nodo seguida de uma verificação na propriedade do fator de balanceamento. Caso não obedeça a essa propriedade, deve-se fazer uma rotação conveniente.

Dada uma raiz r com subárvores L e R, e supondo que a inserção deve ser feita na sub-árvore da esquerda. Podemos distinguir 3 casos:

       1 - Se hL = hR, então L e R ficam com alturas diferentes mas continuam balanceadas.

       2 - Se hL < hR, então L e R ficam com alturas iguais e balanceamento foi melhorado.

       3 - Se hL > hR, então L fica ainda maior e balanceamento foi violado.

Na árvore abaixo:

• Nós 9 ou 11 podem ser inseridos sem balanceamento . Subárvore com raiz 10 passa a ter uma subárvore e subárvore com raiz 8 vai ficar melhor balanceada  
• Inserção dos nós 3, 5 ou 7 requerem que a árvore seja rebalanceada

Fator de Balanceamento (FB) de um nó:

É a altura da subárvore direita do nó menos a altura da subárvore esquerda do nó

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:

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.

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: