5 Indexa o Arvore AVL
1589 palavras
7 páginas
Árvores AVLEstrutura de Dados II
Jairo Francisco de Souza
Introdução
As árvores binárias de pesquisa são projetadas para um acesso rápido à informação. Idealmente a árvore deve ser razoavelmente equilibrada e a sua altura será dada (no caso de estar completa) por h=log2(n+1)
O tempo de pesquisa tende a O(log2N)
Porém, com sucessivas inserções de dados principalmente ordenados, ela pode se degenerar para O(n)
Conceito de balanceamento
Árvores completas são aquelas que minimizam o número de comparações efetuadas no pior caso para uma busca com chaves de probabilidades de ocorrências idênticas.
Contudo, para garantir essa propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação sobre seus nós (inclusão ou exclusão).
Conceito de balanceamento
Exemplo:
8
12
4
2
1
6
3
5
10
7
9
14
11
13
Suponha a inclusão da chave 0 (zero).
Conceito de balanceamento
Exemplo:
8
12
4
2
1
0
6
3
5
10
7
9
14
11
13
Conceito de balanceamento
8
Exemplo:
12
4
2
1
6
3
5
10
7
9
14
11
13
0
7
11
3
1
0
5
2
4
9
6
8
13
10
12
14
Conceito de balanceamento
Para reorganizar a árvore anterior, foi utilizada uma abordagem O(n), no pior caso.
Naturalmente, essa é uma péssima solução, uma vez que operações como inserção e remoção geralmente são efetuados em O(logn) passos.
Por esse motivo, árvores completas não são recomendadas para aplicações que requeiram estruturas dinâmicas.
Conceito de balanceamento
Alternativa: utilizar um determinado tipo de árvore binária cujo pior caso para a busca não seja necessariamente tão pequeno quanto o mínimo 1 + lower_bound(logn) passos pela árvore completa.
Contudo, a altura dessa árvore deve ser da mesma ordem de grandeza que a altura de uma árvore completa com o mesmo número de nós.
Ou seja, deve possuir altura O(logn) para todas as suas subárvores. Árvore AVL
A AVL (Adelson-Velskii e Landis – 1962) é uma árvore altamente balanceada, isto é, nas inserções e