Texto enviado para o site

Páginas: 11 (2520 palavras) Publicado: 17 de novembro de 2011
Á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:...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • TEXTO 1 PODE SER ENVIADO OK
  • Leitura e Produ o de texto 7 8 ENVIADO
  • Texto de teste para saber se o site é realmente bom
  • Texto Publicado no Site do CRMV SP em 10 04 15 1
  • Site chato fica fazendo eu fazer essa coisa pra ver o texto
  • Site
  • Site
  • Site

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!