QUESTIONÁRIO 4 - Á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 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?

R: Uma arvore AVL é uma arvore binária de busca , (ABB) , auto balanceada , construída de tal modo que a altura de sua subarvore direita difere da altura de sua subarvore esquerda de no máximo 1.

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.

R: Seja c uma nova chave a inserir numa árvore AVL A. Primeiro, c é inserido como folha de A, seguindo o algoritmo 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.

R:A rotação simples segue apenas uma sub-árvore ou seja pela sub-árvore esquerda ou pela sub-árvore direita. Já a rotação dupla segue para ambos os lados da sub-árvore.

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.

R: O passo inicial da remoção consiste em seguir o procedimento aplicado no caso geral de uma ABB. é sempre uma folha que é eliminada da árvore (mesmo quando o valor removido está num nó interior, neste caso o conteúdo de uma folha é transferida nesse nó e a folha é removida). Portanto, a altura das sub arvores que contém esta folha pode ser alterada, e pode ser necessário reequilibrar a árvore, com operações de rotação.

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

R: