Árvores AVL

Árvores AVL

Estrutura de Dados e Arquivos

1

Árvores
Um árvore é uma estrutura de dados bidimensional, não linear que

possui propriedades especiais e admite algumas operações de conjuntos dinâmicos, como consulta, inserção, remoção e outros.

Árvore Simples Desordenada

Estrutura de Dados e Arquivos

2

Degeneração
Sucessivas inserções e remoções de nós em uma árvore fazem com que existam diferenças entre os níveis das suas folhas, o que acarreta grandes diferenças de performance no acesso a seus nós. No pior caso, se os dados já estão ordenados, a árvore será uma lista, perdendo toda a eficiência da busca.
Nesses casos, diz-se que a árvore ficou degenerada.

Árvore Degenerada
Estrutura de Dados e Arquivos

3

Árvores Balanceadas

Uma árvore é dita balanceada quando, para qualquer nó, as suas sub-árvores à esquerda e à direita possuem a mesma altura. Isso equivale a

dizer que todos os ponteiros nulos estão no mesmo nível, ou seja, que a árvore está completa. Isso nem sempre é possível, por conta do número de

nós da árvore.

Um critério mais simplificado seria considerar uma árvore balanceada se o número máximo de nós da sub-árvore esquerda diferencie no máximo 1

da sub-árvore direita.

Estrutura de Dados e Arquivos

4

Fator de Balanceamento

O Fator de Balanceamento (FB) de um nó é obtido pela diferença da

altura da subárvore direita do nó e a altura da subárvore esquerda do mesmo.
O FB de uma folha é sempre zero.
𝐹𝐵 𝑛ó 𝑝 = 𝑎𝑙𝑡𝑢𝑟𝑎 𝑠𝑢𝑏á𝑟𝑣𝑜𝑟𝑒 𝑑𝑖𝑟𝑒𝑖𝑡𝑎 𝑝 − 𝑎𝑙𝑡𝑢𝑟𝑎(𝑠𝑢𝑏á𝑟𝑣𝑜𝑟𝑒 𝑒𝑠𝑞𝑢𝑒𝑟𝑑𝑎 𝑝)

Estrutura de Dados e Arquivos

5

AVL
A sigla que denomina este tipo de árvore provem dos nomes de seus

criadores, Georgy Adelson-Velsky e Yevgeniy Landis. A primeira referência feita a este tipo de estrutura encontra-se no artigo “Algoritmos para

organização da informação”, de 1962.

Adelson-Velsky
Landis
Estrutura de Dados e Arquivos

6

AVL

As