O que são indices em Árvore?

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.

O que é ABB e AVL?

Á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:

void emOrdem(struct No *pNo) {
    if(pNo != NULL) {
        emOrdem(pNo→pEsquerda);
        visita(pNo);
        emOrdem(pNo→pDireita);
    }
}

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.

Á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.

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

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.