Exibir código-fonte para Índices em Árvore

= O que são indices em Árvore? =
<br>

* São índices baseados em famílias de árvores que permitem armazenamento e busca de dados com relativa facilidade.
* O objetivo dessas estruturas é obter uma performance média bem melhor que aquela obtida com listas sequenciais. 
* O mecanismo básico utilizado nas árvores de busca é o de, numa procura, comparar o argumento de busca com determinada chave de determinado nó da árvore. 
** Se a chave for maior, a busca prossegue pela subárvore da direita
** Se for menor, pela subárvore da esquerda. 
<br>

= O que é ABB e AVL? =
<br>

== ABB ==
<br>

* Árvore  Binária  de Busca (ABB) é uma árvore binária onde as chaves dos nós da subárvore direita de cada nó são maiores que as chaves desse  nó e as chaves da subárvore esquerda são menores que a mesma.
* Uma árvore binária que não é ABB é aquela cuja chave A está na raiz e existem chaves maiores que A na subárvore esquerda. Um exemplo de ABB é mostrado a seguir:
<br>

[[Arquivo:ABB.png]]
<br>

* Propriedades:
** Propriedade 1: O percurso em ordem simétrica de uma ABB fornece as chaves ordenadas.
*** Essa propriedade decorre diretamente da definição da árvore e é base para um método de Ordenação (TreeSort) que consiste em criar uma ABB com as chaves e depois percorrer a ABB em ordem simétrica. A análise deste método fica como exercício. 
** Na árvore usada como exemplo, esse percurso fornece em ordem simétrica:
*** 1 3 4 6 7 8 10 13 14
*** Algoritmo em C: 
 void emOrdem(struct No *pNo) {
     if(pNo != NULL) {
         emOrdem(pNo→pEsquerda);
         visita(pNo);
         emOrdem(pNo→pDireita);
     }
 }


* Em pré-ordem:
** 8 3 1 6 4 7 10 14 13
*** Algoritmo em C: 
 void preOrdem(Struct No *pNo){
     if(pNo != NULL){
         visita(pNo);
         preOrdem(pNo→pEsquerda);
         preOrdem(pNo→pDireita);
     }
  }

* Outra propriedade importante ( na verdade, mais um resumo da análise do algoritmo feita) diz respeito à altura da árvore:
** Propriedade 2: A altura de uma ABB com n chaves varia entre log2n  e  n.
*** Esse foi um resultado mostrado na análise do algoritmo de busca. A melhor árvore que pode ser obtida é uma árvore com o mesmo parâmetro de uma árvore completa. Essa árvore corresponde à Pesquisa Binária em um vetor. Já a pior árvore corresponde a uma árvore de altura n, correspondendo à Busca sequencial. Entretanto, o caso médio deste tipo de estrutura é razoável ( árvore com altura = 1.4 log2n.
*** A possibilidade de termos árvores degeneradas é que levará à introdução de árvores balanceadas, árvores AVL, por exemplo.

* Propriedade 3: A estrutura de uma ABB depende da ordem de entrada das chaves.
** A nomeação desta propriedade serve para chamar a atenção para o fato explicitado. Se, por exemplo, as chaves forem inseridas em ordem ascendente ou descendente, a árvore resultante é degenerada.
<br>

== AVL ==
<br>

* Árvore AVL é um tipo de árvore de busca binária balanceada. 
* Em tal árvore, a altura de dois nós folha difere no máximo em uma unidade. 
* As operações de busca, inserção e eliminação de elementos possuem complexidade O(logn) no qual n é o número de elementos da árvore. Inserções e eliminações podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.


* Balanceamento
** 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 estiver balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. 
** O balanceamento é requerido para as operações de adição e exclusão de elementos. 
** Para definir o balanceamento é utilizado um fator específico para nós.
** 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 -2 ou 2 é considerado um árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.
<br>

[[Arquivo:avl.png]]

= Vantagens =
<br>

* AVL:
** Algoritmo muito rápido
** Acesso mais rápido aos elementos já que estão organizados pois tem maior eficiência nas operações de busca, pois, sendo a altura da AVL bem menor, o número necessário de comparações diminui sensivelmente.
** Exemplos: Em um árvore desbalanceada de 10.000 nós são necessárias 5.000 comparações para efetuar uma busca. Já na AVL, são necessárias apenas 14 comparações.


* ABB:
** A grande utilidade da árvore binária de busca é armazenar dados contra os quais outros  dados são freqüentemente verificados (busca!)
** Em uma ABB é possível encontrar qualquer chave existente caminhando na árvore:
** A escolha da direção de busca só depende da chave que se procura e da chave que o nó atual possui
<br>

= Desvantagens =
<br>

* AVL
** A codificação de uma AVL necessita que o cálculo da altura seja constante caso contrário será eficiente nas buscas e ineficiente nas inserções e remoções


* ABB:
** O desempenho depende da ordem com que os elementos foram inseridos
** Inserções (como folhas) e Eliminações (mais complexas) causam desbalanceamento.
<br>

= Referências bibliográficas =
<br>

* [1] Oliveira, Karina. Algoritmos e Estrutura de Dados II. Unicap. PE.
* [2] Maldonado, Yandre  e Costa, Gomes da. Árvores. UEM. Maringá.