Índices em Árvore

Yuri 

O que são indices em Árvore?

• São índices baseados em árvores de busca que são famílias de árvores utilizadas para armazenamento e busca de dados.
• 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:
    • A B C D E F G H I
    • 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 e árvores B), nos próximos ítens.
  • 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