Árvores AVL: Balanceamento de Árvores de Busca

Prévia do material em texto

AULA 21
ESTRUTURA DE DADOS
Árvores AVL
Norton T. Roman & Luciano A. Digiampietri
Árvores AVL
Vimos que a ordem de inserção determina o formato de
uma Árvore de Busca Binária
8
12
15
20
23
28
8
12
15
20
23
28
Árvores AVL
Vimos também que isso
era a diferença entre ela
se comportar como numa
busca binária ou numa
sequencial
8
12
15
20
23
28
8
12
15
20
23
28
Árvores AVL
Balanceamento é importante
Contudo, um
balanceamento perfeito é
algo computacionalmente
caro
2
8
12
15
20
23
28
Árvores AVL
Balanceamento é importante
Contudo, um
balanceamento perfeito é
algo computacionalmente
caro
2
8
12
15
20
23
28
Árvores AVL
Que fazer?
Nada... você está com sorte hoje?
Ou podemos permitir um “bom” balanceamento
Em que pode haver um pouco de desbalanceamento
Algoritmo de Adelson-Velskii e Landis (as Árvores
AVL)
Árvores AVL
Que fazer?
Nada... você está com sorte hoje?
Ou podemos permitir um “bom” balanceamento
Em que pode haver um pouco de desbalanceamento
Algoritmo de Adelson-Velskii e Landis (as Árvores
AVL)
Árvores AVL
Que fazer?
Nada... você está com sorte hoje?
Ou podemos permitir um “bom” balanceamento
Em que pode haver um pouco de desbalanceamento
Algoritmo de Adelson-Velskii e Landis (as Árvores
AVL)
Árvores AVL
Que fazer?
Nada... você está com sorte hoje?
Ou podemos permitir um “bom” balanceamento
Em que pode haver um pouco de desbalanceamento
Algoritmo de Adelson-Velskii e Landis (as Árvores
AVL)
Árvores AVL
Que fazer?
Nada... você está com sorte hoje?
Ou podemos permitir um “bom” balanceamento
Em que pode haver um pouco de desbalanceamento
Algoritmo de Adelson-Velskii e Landis (as Árvores
AVL)
Árvores AVL
AVL é uma árvore de busca binária balanceada com
relação à altura de suas subárvores
Uma árvore AVL verifica a altura das subárvores da
esquerda e da direita, garantindo que essa diferença
não seja maior que ±1
Esta diferença é seu Fator de Balanceamento
fb = hesq − hdir
Árvores AVL
AVL é uma árvore de busca binária balanceada com
relação à altura de suas subárvores
Uma árvore AVL verifica a altura das subárvores da
esquerda e da direita, garantindo que essa diferença
não seja maior que ±1
Esta diferença é seu Fator de Balanceamento
fb = hesq − hdir
Árvores AVL
AVL é uma árvore de busca binária balanceada com
relação à altura de suas subárvores
Uma árvore AVL verifica a altura das subárvores da
esquerda e da direita, garantindo que essa diferença
não seja maior que ±1
Esta diferença é seu Fator de Balanceamento
fb = hesq − hdir
Árvores AVL
AVL é uma árvore de busca binária balanceada com
relação à altura de suas subárvores
Uma árvore AVL verifica a altura das subárvores da
esquerda e da direita, garantindo que essa diferença
não seja maior que ±1
Esta diferença é seu Fator de Balanceamento
fb = hesq − hdir
Árvores AVL
O fator de balanceamento é calculado a cada nó
E, para cada nó, a diferença de altura entre a
subárvore da esquerda e da direita não pode passar
de ±1
Lembrando que a altura de uma árvore vazia é -1
O fator de balanceamento, ou alternativamente a
altura do nó, é armazenada no próprio nó
Árvores AVL
O fator de balanceamento é calculado a cada nó
E, para cada nó, a diferença de altura entre a
subárvore da esquerda e da direita não pode passar
de ±1
Lembrando que a altura de uma árvore vazia é -1
O fator de balanceamento, ou alternativamente a
altura do nó, é armazenada no próprio nó
Árvores AVL
O fator de balanceamento é calculado a cada nó
E, para cada nó, a diferença de altura entre a
subárvore da esquerda e da direita não pode passar
de ±1
Lembrando que a altura de uma árvore vazia é -1
O fator de balanceamento, ou alternativamente a
altura do nó, é armazenada no próprio nó
Árvores AVL
O fator de balanceamento é calculado a cada nó
E, para cada nó, a diferença de altura entre a
subárvore da esquerda e da direita não pode passar
de ±1
Lembrando que a altura de uma árvore vazia é -1
O fator de balanceamento, ou alternativamente a
altura do nó, é armazenada no próprio nó
Árvores AVL
2
8
12
15
23
0 0
1 0
2
AVL
2
8
12
15
20
23
0 0
1 1
2
0
AVL
Árvores AVL
2
8
12
15
23
0 0
1 0
2
AVL
2
8
12
15
20
23
0 0
1 1
2
0
AVL
Árvores AVL
2
8
12
15
23
0 0
1 0
2
AVL
2
8
12
15
20
23
0 0
1 1
2
0
AVL
Árvores AVL
2
8
12
15
20
23
0 0
1 1
2
0
AVL
2
8
12
15
20
23
18
0 0
1 2
3
1
0
-1
Não AVL
Árvores AVL
2
8
12
15
20
23
0 0
1 1
2
0
AVL
2
8
12
15
20
23
18
0 0
1 2
3
1
0
-1
Não AVL
Árvores AVL
Note que, nesse caso, a inserção de um único elemento
foi o suficiente para fazer com que uma árvore deixasse
de ser AVL
2
8
12
15
20
23
0 0
1 1
2
0 2
8
12
15
20
23
18
0 0
1 2
3
1
0
Árvores AVL
Uma inserção pode fazer com que o fator de
balanceamento de um nó vire ±2
Contudo, somente nós no
caminho do ponto de
inserção até a raiz podem
ter mudado sua altura
2
8
12
15
20
23
18
0 0
1 2
3
1
0
Árvores AVL
Uma inserção pode fazer com que o fator de
balanceamento de um nó vire ±2
Contudo, somente nós no
caminho do ponto de
inserção até a raiz podem
ter mudado sua altura
2
8
12
15
20
23
18
0 0
1 2
3
1
0
Árvores AVL
Então, após a inserção, voltamos até a raiz, nó por nó,
atualizando as alturas
Se um novo fator de
balanceamento para um
determinado nó for 2 ou
-2, ajustamos a árvore
rotacionando em torno
desse nó
2
8
12
15
20
23
18
0 0
1 2
3
1
0
Árvores AVL
Então, após a inserção, voltamos até a raiz, nó por nó,
atualizando as alturas
Se um novo fator de
balanceamento para um
determinado nó for 2 ou
-2, ajustamos a árvore
rotacionando em torno
desse nó
2
8
12
15
20
23
18
0 0
1 2
3
1
0
Árvores AVL – Rotação
Existem dois tipos de rotação:
Rotação à esquerda
x
yα
β γ
y
x
α β
γ
Rotação à direita
x
yα
β γ
y
x
α β
γ
Árvores AVL – Rotação
Existem dois tipos de rotação:
Rotação à esquerda
x
yα
β γ
y
x
α β
γ
Rotação à direita
x
yα
β γ
y
x
α β
γ
Árvores AVL – Rotação
Existem dois tipos de rotação:
Rotação à esquerda
x
yα
β γ
y
x
α β
γ
Rotação à direita
x
yα
β γ
y
x
α β
γ
Árvores AVL – Rotação
2
8
12
15
20
23
18
0 0
1 2
3
1
0
2
8
12
15
20
2318
0 0
1
0
2
1
0
Árvores AVL – Rotação
2
8
12
15
20
23
18
0 0
1 2
3
1
0
2
8
12
15
20
2318
0 0
1
0
2
1
0
Temos um desequilíbrio (fator de balanceamento 2)
Árvores AVL – Rotação
2
8
12
15
20
23
18
0 0
1 2
3
1
0
2
8
12
15
20
2318
0 0
1
0
2
1
0
Balanceamos rotacionando em torno desse nó
Árvores AVL – Rotação
2
8
12
15
20
23
18
0 0
1 2
3
1
0
2
8
12
15
20
2318
0 0
1
0
2
1
0
Balanceamos rotacionando em torno desse nó
Árvores AVL – Rotação
Considere a árvore AVL
ao lado:
O que pode acontecer se
inserimos um elemento
em α?
Quebramos o
balanceamento em x
y
x
α β
γ
h+1
h+2
h h
h
Árvores AVL – Rotação
Considere a árvore AVL
ao lado:
O que pode acontecer se
inserimos um elemento
em α?
Quebramos o
balanceamento em x
y
x
α β
γ
h+1
h+2
h h
h
Árvores AVL – Rotação
Considere a árvore AVL
ao lado:
O que pode acontecer se
inserimos um elemento
em α?
Quebramos o
balanceamento em x
y
x
α β
γ
h+2
h+3
h+1 h
h
Árvores AVL – Rotação
Considere a árvore AVL
ao lado:
O que pode acontecer se
inserimos um elemento
em α?
Quebramos o
balanceamento em x
y
x
α β
γ
h+2
h+3
h+1 h
h
Árvores AVL – Rotação
Como consertamos isso?
Fazendo a rotação à
direita
E assim “erguendo” a
parte que havia ficado
maior
y
x
α β
γ
h+2
h+3
h+1 h
h
Árvores AVL – Rotação
Como consertamos isso?
Fazendo a rotação à
direita
E assim “erguendo” a
parte que havia ficado
maior
y
x
α β
γ
h+2
h+3
h+1 h
h
Árvores AVL – Rotação
Como consertamos isso?
Fazendo a rotação à
direita
E assim “erguendo” a
parte que havia ficado
maior
y
x
α β
γ
h+2
h+3
h+1 h
h
Árvores AVL – Rotação
Como consertamos isso?
Fazendoa rotação à
direita
E assim “erguendo” a
parte que havia ficado
maior
y
x
α
β γ
h+2
h+1
h+1
h h
Árvores AVL – Rotação
Como consertamos isso?
Fazendo a rotação à
direita
E assim “erguendo” a
parte que havia ficado
maior
y
x
α
β γ
h+2
h+1
h+1
h h
Árvores AVL – Rotação
Inserções na parte mais externa da árvore são
resolvidas com rotações simples
Na subárvore esquerda
do filho esquerdo do nó
desbalanceado
Na subárvore direita do
filho direito desse nó
y
x
α
αα
β
z
γ
Árvores AVL – Rotação
Inserções na parte mais externa da árvore são
resolvidas com rotações simples
Na subárvore esquerda
do filho esquerdo do nó
desbalanceado
Na subárvore direita do
filho direito desse nó
y
x
α
α
α
β
z
γ
Árvores AVL – Rotação
Inserções na parte mais externa da árvore são
resolvidas com rotações simples
Na subárvore esquerda
do filho esquerdo do nó
desbalanceado
Na subárvore direita do
filho direito desse nó
y
x
αα
α β
z
γ
Árvores AVL – Rotação
E quando a inserção é na parte mais interna?
Na subárvore direita do
filho esquerdo do nó
desbalanceado
Na subárvore esquerda
do filho direito desse nó
y
x
α β
z
δγ
Árvores AVL – Rotação
E quando a inserção é na parte mais interna?
Na subárvore direita do
filho esquerdo do nó
desbalanceado
Na subárvore esquerda
do filho direito desse nó
y
x
α β
z
δγ
Árvores AVL – Rotação
E quando a inserção é na parte mais interna?
Na subárvore direita do
filho esquerdo do nó
desbalanceado
Na subárvore esquerda
do filho direito desse nó
y
x
α β
z
δγ
Árvores AVL – Rotação
Voltemos à nossa árvore
AVL...
O que pode acontecer se
inserimos um elemento
em β?
Quebramos novamente o
balanceamento em x
y
x
α β
γ
h+1
h+2
hh
h
Árvores AVL – Rotação
Voltemos à nossa árvore
AVL...
O que pode acontecer se
inserimos um elemento
em β?
Quebramos novamente o
balanceamento em x
y
x
α β
γ
h+1
h+2
hh
h
Árvores AVL – Rotação
Voltemos à nossa árvore
AVL...
O que pode acontecer se
inserimos um elemento
em β?
Quebramos novamente o
balanceamento em x
y
x
α β
γ
h+2
h+3
h+1h
h
Árvores AVL – Rotação
Voltemos à nossa árvore
AVL...
O que pode acontecer se
inserimos um elemento
em β?
Quebramos novamente o
balanceamento em x
y
x
α β
γ
h+2
h+3
h+1h
h
Árvores AVL – Rotação
Como consertamos isso?
Tentemos a rotação à
direita
E tudo que fizemos foi
mudar o ponto de
desequilíbrio
y
x
α β
γ
h+2
h+3
h h+1
h
Árvores AVL – Rotação
Como consertamos isso?
Tentemos a rotação à
direita
E tudo que fizemos foi
mudar o ponto de
desequilíbrio
y
x
α β
γ
h+2
h+3
h h+1
h
Árvores AVL – Rotação
Como consertamos isso?
Tentemos a rotação à
direita
E tudo que fizemos foi
mudar o ponto de
desequilíbrio
y
x
α β
γ
h+2
h+3
h h+1
h
Árvores AVL – Rotação
Como consertamos isso?
Tentemos a rotação à
direita
E tudo que fizemos foi
mudar o ponto de
desequilíbrio
y
x
α
β γ
h+3
h+2
h
h+1 h
Árvores AVL – Rotação
Como consertamos isso?
Tentemos a rotação à
direita
E tudo que fizemos foi
mudar o ponto de
desequilíbrio
y
x
α
β γ
h+3
h+2
h
h+1 h
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
y
x
β
γ
α
h+2
h+3
h h+1
h
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
y
x
γ
z
�δ
α
h+2
h+3
h
h
h+1
h ou h-1
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
y
x
γ
z
�δ
α
h+2
h+3
h
h
h+1
h ou h-1
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
x
γ
z
y �
δα
h+1
h+3
h
h
h+2
h ou h-1
h ou h-1
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
z
y
x
α
γ
�
δ
h+1
h+3
h
h
h+2
h ou h-1
h ou h-1
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita...
feito!
z
y x
α γ�δ
h+1 h+1
h h
h+2
h ou h-1
Árvores AVL – Rotação
Vamos olhar mais de
perto a estrutura de β
Façamos uma rotação à
esquerda
Seguida de uma rotação à
direita... feito!
z
y x
α γ�δ
h+1 h+1
h h
h+2
h ou h-1
Árvores AVL – Rotação
Então, enquanto inserções na parte mais externa da
árvore são resolvidas com rotações simples
Inserções na parte mais interna da árvore são
resolvidas com rotações duplas
Árvores AVL – Rotação
Em suma...
Fazemos uma rotação à esquerda se um nó foi
inserido na subárvore direita do filho à direita
B
A
C
B
A
C
B
A C
Árvores AVL – Rotação
Em suma...
Fazemos uma rotação à esquerda se um nó foi
inserido na subárvore direita do filho à direita
B
A
C
B
A
C
B
A C
Árvores AVL – Rotação
Em suma...
Fazemos uma rotação à direita se um nó foi inserido
na subárvore esquerda do filho à esquerda
B
A
C
B
A
C
B
AC
Árvores AVL – Rotação
Em suma...
Fazemos uma rotação esquerda-direita se um nó foi
inserido na subárvore direita do filho à esquerda
B
A
C
B
A
C
C
A
B
C
AB
Árvores AVL – Rotação
Em suma...
Fazemos uma rotação direita-esquerda se um nó foi
inserido na subárvore esquerda do filho à direita
B
A
C
B
A
C
C
A
B
C
BA
AULA 21
ESTRUTURA DE DADOS
Árvores AVL
Norton T. Roman & Luciano A. Digiampietri