Inf01203 Aula24 Avl

Árvores Binárias de Pesquisa

Árvores
Balanceadas

• Apresentam uma relação de ordem
• A ordem é definida pela chave
• Operações:
500

– inserir
– consultar
– excluir

300

150
Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

800

400

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Problemas com ABP

Problemas com ABP

Exemplo:

• Desbalanceamento progressivo
• Exemplo:

– Inserção: 10, 5, 15, 20, 25, 30, 35
– Inserção: 1, 13, 24, 27, 56

600

900

Estruturas de Dados - Àrvores

– inserção: 1, 13, 24, 27, 56
1
13

Alternativa de solução:
• Árvores balanceadas
• AVL

24
27

56
Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Balanceamento de
Árvores

Por Freqüência

• Distribuição equilibrada dos nós

• Por freqüência de acesso

– otimizar as operações de consulta
– diminuir o número médio de comparações

– Pressupõe distribuição não uniforme de acessos
500

50%

• Distribuição
12%

– uniforme
– não uniforme

400

25%
Balanceamento por distribuição de acessos!

4%

• chaves mais solicitadas mais perto da raiz

550

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

800

Estruturas de Dados - Àrvores

Árvores balanceadas por ALTURA

600

900

5%

4%

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Por Freqüência X Por Altura

Uma árvore binária é

completamente balanceada

500

se a distância média dos nodos até a raiz for mínima
12%

400

4%

550

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

50%

800

600

800

25%

900

50%

5%

4%

400

500

50%

600

4% 550

4%

900

5%

4%

Renata de Matos Galante, Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel