5 Indexa o Arvore AVL

1589 palavras 7 páginas
Árvores AVL
Estrutura 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

Relacionados

  • dasdsa
    1874 palavras | 8 páginas
  • BANCO DE DADOS RAIDS
    2684 palavras | 11 páginas
  • tecnologia
    11131 palavras | 45 páginas
  • linguagem de programação orientada a objeto lpoo
    7084 palavras | 29 páginas
  • Sistema De Banco De Dados Ramez Elmasri E Shamkant B
    432650 palavras | 1731 páginas