Árvores binárias equilibradas

Aula 11 – Árvores Binárias Balanceadas (AVL)Árvores Binárias Balanceadas (ou Árvores AVL)

• Sucessivas inserções e retiradas fazem com que existam diferenças

sensíveis entre os níveis das suas folhas, o que acarreta grandes

diferenças de performance no acesso aos seus nós.

• Uma árvore é dita balanceada quando para qualquer nó, as suas sub-

árvores à esquerda e à direita possuem a mesma altura.Implementação de Árvores com Vetores

• Para estabelecer os endereços, basta conhecer o endereço do nó pai.

• No exemplo, a raiz da árvore (A) está no índice zero do vetor.

• Se i é o endereço do pai, 2i + 1 é o endereço do filho da esquerda e 2i + 2

é o endereço do filho da direita.Árvores Balanceadas - Contexto

• As ABB têm uma séria desvantagem que pode afetar o

tempo necessário para recuperar um item armazenado.

• A desvantagem é que o desempenho da ABB depende da

ordem em que os elementos são inseridos.

1

4

2

3

2

4

1

5

6

7

6

3

5

7Árvores Balanceadas - Contexto

• Idealmente, deseja-se que a árvore esteja balanceada, para

qualquer nó p da árvore.

• Como saber se a árvore está balanceada ?

• Para cada nó p da árvore a altura da sua sae é

aproximadamente igual à altura da sua sad.Árvores Binárias Balanceadas (ou Árvores AVL)

• O nome AVL vem de seus criadores (matemáticos russos)

Adelson, Velsky e Landis (1962).

– Uma árvore binária de pesquisa T é denominada AVL se:

Para todos nós de T, as alturas de suas duas sub-árvores

diferem no máximo de uma unidade.Como reconhecer uma árvore desbalanceada?

• Como saber se a árvore está desbalanceada ?

– Verificando se existe algum nó “desregulado”.

• Como saber se um nó está desregulado ?

– Subtraindo-se as alturas das suas sub-árvores.

• Por questões de eficiência, estas diferenças são pré-

calculadas