Texto enviado para o site

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2520 palavras )
  • Download(s) : 0
  • Publicado : 17 de novembro de 2011
Ler documento completo
Amostra do texto
Árvores Balanceadas

Árvores Binárias de Pesquisa
• Apresentam uma relação de ordem • A ordem é definida pela chave • Operações:
– inserir – consultar – excluir
500

300

800

150
Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel Estruturas de Dados - Àrvores Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

400

600

900

Estruturas de Dados - Àrvores

Problemas comABP
• Desbalanceamento progressivo • Exemplo:
– inserção: 1, 13, 24, 27, 56
1 13 24 27 56
Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel Estruturas de Dados - Àrvores

Balanceamento de Árvores
• Distribuição equilibrada dos nós
– otimizar as operações de consulta – diminuir o número médio de comparações

• Distribuição
Alternativa de solução: • Árvores balanceadas • AVL – uniforme –não uniforme
• chaves mais solicitadas mais perto da raiz

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Por Freqüência
• Por freqüência de acesso
– Pressupõe distribuição não uniforme de acessos
500 50%

Árvores balanceadas por ALTURA
Uma árvore binária é

completamente balanceada
se a distância média dos nodos até a raiz for mínima

12%400

800

25% Balanceamento por distribuição de acessos!

4%

600

900

5%

550

4%

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Por Freqüência X Por Altura
500 50% 800 50%

Balanceamento por ALTURA
220 120 300

100 12% 400 800 25% 50% 500 6004% 80 4% 600 900 5% 4% 400 4% 550 900 5% 110 130

150

260

400

200

250

270

350

140 550 4%

Árvore não completamente balanceada

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Árvores AVL

Adelson-Velskii e Landis (1962)

Árvores AVL
AVLAdelson-Velskii e Landis (1962)

• árvores FATOR(1) são chamadas Árvores AVL
Uma árvore AVL é uma árvore binária de pesquisa (ABP) construída de tal modo que a altura de sua subárvore direita difere da altura da subárvore esquerda de no máximo 1. 1

AVL

¬ AVL
Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel Estruturas de Dados - Àrvores Clesio S. Santos, Nina Edelweiss e Luciana P.Nedel Estruturas de Dados - Àrvores

Árvores balanceadas por altura
HB(k)-Tree → Height-Balanced k -Tree

Árvores balanceadas por altura
HB(k)-Tree → Height-Balanced k -Tree
A B D G I E H J C

• árvore binária • para qualquer nodo, as alturas de suas duas
subárvores não diferem de mais do que k unidades • cada uma das subárvores do nodo apresenta a propriedade FATOR(k)

• árvore binária• para qualquer nodo, as alturas de suas duas
subárvores não diferem de mais do que k unidades • cada uma das subárvores do nodo apresenta a propriedade FATOR(k) Ex: verificar se a árvore ao lado é
FATOR(1) FATOR(2) FATOR(3) → Não → Não → Sim
-2

A +3
0

B
-1

C E

0

D
0

G
0

H 0 I J 0

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - ÀrvoresClesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Árvores AVL

Adelson-Velskii e Landis (1962)

Exercício:
Verifique quais das ABP são AVL:
130 120

• árvores FATOR(1) são chamadas Árvores AVL
Uma árvore AVL é uma árvore binária de pesquisa (ABP) construída de tal modo que a altura de sua subárvore direita difere da altura da subárvore esquerda deno máximo 1. 1

100

150

100

130

80

120

200

80

110

200

110

150

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Clesio S. Santos, Nina Edelweiss e Luciana P. Nedel

Estruturas de Dados - Àrvores

Exercício: Resposta
Verifique quais das ABP são AVL:
130

Exercício
42 15 6 27 20

Verifique quais das ABP são AVL:...
tracking img