Índices em Árvore

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?

ABB

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

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

AVL

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

Vantagens

• 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

Desvantagens

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

Referências bibliográficas

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