Informatica

Pesquisa e Ordenação
Pesquisa em Memória Primária
Aula 08

Árvores Balanceadas

Referência: EDELWEIS, N.; GALANTE, R. Estruturas de dados. Porto Alegre: Bookman, 2009.

Balanceamento em Árvores
 Distribuição equilibrada dos nodos
⌂ otimizar as operações de consulta ⌂ diminuir o número médio de comparações

 Distribuição
⌂ Balanceamento por altura – uniforme - AVL ⌂ Balanceamento por frequência – não uniforme

Árvores Balanceadas por Altura
 Todas as folhas estão à mesma distância da raiz, ou distância semelhante.  Uma árvore binária é completamente balanceada se a distância média dos nodos até a raiz for mínima.

Árvores Balanceadas por Frequência
 Por frequência de acesso:
⌂ Pressupõe distribuição não uniforme de acessos.

500 50%
12% 400 4% 600

800 25% 900 5%

Balanceamento por frequência de acessos

550 4%

Balanceamento por Frequência x Altura
 Por frequência de acesso:
⌂ Pressupõe distribuição não uniforme de acessos.

500 50%
12% 400 4% 600

800 25% 900 5%

800 50%
50% 500 4% 400 4% 550

600 4%

900 5%

550 4%

Problemas com Árvores Binárias de Pesquisa
 Inserções podem gerar ABP (Árvores Binárias de Pesquisa) muito desbalanceadas por altura.  Exemplos: 10
⌂ Inserção: 10, 5, 15, 20, 25, 30 5 15 20 ⌂ Inserção: 1, 13, 24, 27, 56 1 13 24 27 56 25 30

Problemas com Árvores Binárias de Pesquisa
 Árvore binária com limitação de desbalanceamento.  Grau ou fator de desbalanceamento: FB(k).  Para qualquer nodo, a altura das subárvores não difere de mais do que k unidades.  Exemplo: a árvore da figura é
⌂ FB(2)?
• Não 2 B

A 3

C 0 E

⌂ FB(3)?
• Sim

D
0

1

⌂ FB(4)?
• Não

F
0 H

G 0
0

I

Árvore K-Balanceada
 Cálculo do fator de desbalanceamento para cada nodo:
(altura da subárvore da direita) menos (altura da subárvore da esquerda)

130 -1 1 100 0 80 -1 120 150 1 0 100

120 1 130 2 200 -1

200 0 0 80

0 110
0 150 (b) FB(2)

0 110

(a) FB(1)