Texto enviado para o site
2520 palavras
11 páginas
Á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 com ABP
• 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 600 4% 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
AVL