Aula24 25 PesquisaArvoreAVL

Pesquisa em
Memória Primária –
Árvores AVL
David Menotti
Algoritmos e Estruturas de Dados I v DECOM – UFOP

6
8

3

4

z

Árvore AVL




Árvore binária de busca tal que, para qualquer nó interno v, a diferença das alturas dos filhos de v é no máximo 1.
Árvores AVL são balanceadas 44
2

4

17

78
32

1

2
1

48

3

88

50
62

1

1

Exemplo: números próximo dos nós são suas alturas.
© David Menotti

Algoritmos e Estrutura de Dados

Árvores Binárias
Balanceadas e AVL
Inserindo os nós 30, 20, 40, 10, 25, 35 e 50 nesta ordem, teremos:
30
20
10

© David Menotti

40
25

35

50

Algoritmos e Estrutura de Dados

Árvores Binárias
Balanceadas e AVL
Inserindo os nós 10, 20, 30, 40 e 50 nesta ordem, teremos: 10
20
30
40
50
© David Menotti

Algoritmos e Estrutura de Dados

Árvores Binárias
Balanceadas
•

•

•

Existem ordens de inserção de nós que conservam o balanceamento de uma árvore binária. Na prática é impossível prever essa ordem ou até alterá-la.
Algoritmos para balanceamentos.

© David Menotti

Algoritmos e Estrutura de Dados

Árvores Binárias
Balanceadas
•

•

•

A vantagem de uma árvore balanceada com relação a uma degenerada está em sua eficiência. Por exemplo: numa árvore binária degenerada de 10.000 nós são necessárias, em média,
5.000 comparações (semelhança com arrays ordenados e listas encadeadas).
Numa árvore balanceada com o mesmo número de nós essa média reduz-se a 14 comparações.

© David Menotti

Algoritmos e Estrutura de Dados

AVL
•

•

•

Algoritmo de balanceamento de árvores binárias. A origem da denominação AVL vem dos seus dois criadores: Adel’son-Vel’skii e Landis.
Ano de divulgação: 1962.

© David Menotti

Algoritmos e Estrutura de Dados

TAD-Árvore AVL


Estrutura de dados:

typedef long TipoChave; typedef struct Registro {
TipoChave Chave;
/* outros componentes */
} Registro;

typedef Struct No {
Registro Reg;
Apontador pEsq, pDir;
} No;

typedef struct No * Apontador; typedef Apontador TipoDicionario;

© David Menotti

Algoritmos e