Árvores genéricas

Algoritmos e Estruturas de Dados II Árvores - AVL
Prof. Raimundo BARRETO DCC/ICE/UFAM

Introdução
Árvore Balanceada

• Uma árvore binária balanceada é aquela em que, para

qualquer nó, suas sub-árvores esquerda e direita têm a mesma altura.

Árvore AVL

• Uma árvore binária de busca é considerada balanceada • quando, para cada nó, as alturas de suas sub-árvores esquerda e direita diferem de, no máximo, 1. Essa diferença é chamada fator de balanceamento, ou FB(n).

Introdução

Seja um nó n qualquer da árvore:

•FB(n) = altura(sad) – altura(sae). • se FB(n) = 0, as duas sub-árvores têm a mesma altura; • se FB(n) = -1, a sub-árvore esquerda é mais alta que a direita em 1; • se FB(n) = +1, a sub-árvore direita é mais alta que a esquerda em 1.

Introdução - Exemplo 1
Montar uma ABB, inserindo, sucessivamente, os valores seguintes, na ordem dada, e determinar o fator de balanceamento de cada nó: 30, 20, 40, 10, 35, 25, 22 e 50.

Introdução

Exemplos de Árvores AVL

Introdução

Exemplos de Árvores Não-AVL

Introdução
A vantagem de uma árvore AVL sobre uma degenerada está na maior eficiência nas suas operações de busca, pois, sendo a altura da AVL bem menor, o número necessário de comparações diminui sensivelmente. Por exemplo, numa árvore degenerada de 10.000 nós, são necessárias, em média, 5.000 comparações, numa busca; numa árvore AVL, com o mesmo número de nós, essa média baixa para 14. A solução é adotar um algoritmo que, a cada inserção, faça as correções necessárias para manter sempre a árvore como uma árvore AVL, ou seja, onde qualquer nó n tenha |FB(n)| dir = B->esq; B->esq = A;

A 10
(+2)

A B 20
(+1)

10 B 20 30
(0)

B A 10 30 20 30

Rotação Simples à Direita
A->esq = B->dir; B->dir = A;

(-2)

A 10

A 10 5 B 5 2 2

B A 10

(-1)

B 5

(0)

2

Inserção - Exercício
Mostrar as rotações necessárias para a construção da seguinte árvore AVL: 3, 2, 1, 4, 5, 6 e 7
A B 3
(-1) (-2)

2
(0)

1