Ávores AVL
MC 202 – Estruturas de dados
Cristiano Damaschio Ferreira
[email protected]
Introdução

Árvore binária de busca
Introdução

Árvore binária de busca
AVL


|HR – HL| < 2
Exemplos:
h=2
h=1
h=0
É AVL
h=0
h=0
AVL


|HR – HL| < 2
Exemplos:
h=2
NÃO É AVL
h=1
h=0
h=0
AVL


Fator de balanceamento b = HR – HL
Exemplo:
b=0
b=0
b=0
b = +1
b=0
b=0
AVL

Inserção


Semelhante à inserção em árvore binária de
busca
Pode desbalancear a árvore
AVL

Exemplo

Inserção do valor 5
b=0
b = -1
b=0
b=0
b = +1
b = -2
b=0
b = -1
b=0
b = +1
b=0
AVL

Caso a
AVL

Caso b
AVL

Caso c
AVL

Caso d
AVL

Remanejamento das árvores

Rotação simples à direita

Rotação dupla à direita

Rotação simples à esquerda

Rotação dupla à esquerda
AVL

Rotação simples à direita
AVL

Rotação simples à direita





ne é colocado na raiz
EE permanece a sub-árvore esquerda de ne
n torna-se a raiz da sub-árvore direita de ne
ED torna-se sub-árvore esquerda de n
D permanece a sub-árvore direita de n
AVL

Rotação dupla à direita
AVL

O caso c é similar ao caso a
AVL

O caso d é similar ao caso b
AVL

A remoção é similar à remoção em árvore
binária de busca




Primeiro, busca-se o nó que contém o valor a
ser removido.
Se o nó for folha, remove-o
Se o nó possuir um filho, esse filho substitui o
nó
Senão, busca-se a menor (maior) folha da
sub-árvore direita (esquerda) do nó, substitui
o nó por essa folha
AVL

A remoção pode desbalancear a árvore

Exemplo 1: remover 25
AVL

Exemplo 1
AVL

Exemplo 1
AVL

Exemplo 2:

Retirar 70
AVL

Exemplo 2:
AVL

Exemplo 2:
AVL

Exemplo 3:

Retirar 50
AVL

Exemplo 3:
AVL

Exemplo 3:
AVL

Exemplo 3:
AVL

Exemplo 3: