MC3305
Algoritmos e Estruturas de Dados II
Aula 10 –
Árvores Adelson-Velskii e Landis
Prof. Jesús P. Mena-Chalco
[email protected]
2Q-2014
1
Árvores balanceadas
2
Árvores balanceadas
As ABB permitem buscar de forma eficiente um elemento
dada uma chave.
Deseja-se que o custo de acesso tenha a ordem de grandeza
de uma árvore ótima → O(lg(n))
Este custo deve-se manter ao longo da utilização da
estrutura (inclusive após inserções/remoções).
O custo de ter a estrutura balanceada deve estar na,
idealmente, mesma ordem de grandeza.
Uma árvore binária é balanceada (ou equilibrada) se,
em cada um de seus nós, as subárvores esquerda e direita
tiverem aproximadamente a mesma altura.
3
Árvores balanceadas
Exemplo ruim para o restabablecimento de árvores completas
Para obter esta árvore é
necessário percorrer toda a
árvore, O(n)
Fonte: SZWARCFITER, J. L.; MARKEZON, L. Estruturas de Dados e seus Algoritmos, 3a edição, LTC, 2010.
4
Árvores balanceadas: completas e AVLs
5
AVL
Georgy M. Adelson-Velsky
Russia
Evgenii Mikhailovich Landis
Ucrania
(1922-2014/abril/26)
(1921-1997)
6
AVL
G.M. Adelson-Velskii y E.M. Landis
“An algorithm for the organization of information”.
Proceedings of the USSR Academy of Sciences, vol. 146, pp. 263–266, 1962
AVL foi a primeira estrutura
(conhecida)
de árvore de
altura balanceada/equilibrada.
7
Árvores AVL
Devido ao balanceamento da altura da árvore, as operações
de:
Busca
Inserção
Remoção
em uma árvore com n elementos podem ser efetuadas
em
mesmo no pior caso.
8
Árvores AVL
Devido ao balanceamento da altura da árvore, as operações
de:
Busca
Inserção
Remoção
em uma árvore com n elementos podem ser efetuadas
em
mesmo no pior caso.
Um teorema provado por Adelson-Velskii e Landis garante
que a árvore balanceada nunca será 45% mais alta que a
correspondente árvore perfeitamente balanceada,
independentemente do número de nós existentes.
9
Árvores AVL
Uma árvore AVL é definida como:
Uma árvore vazia é uma árvore AVL.
10
Árvores AVL
Uma árvore AVL é definida como:
Uma árvore vazia é uma árvore AVL.
Sendo T uma ABB, com subárvores esquerda (L) e
direita (R) , T será uma árvore AVL contanto que:
L e R são árvores AVL
A definição de uma ABB de altura equilibrada (AVL)
requer que cada subárvore seja também de altura
equilibrada.
11
Árvores AVL
12
Fator de balanceamento
13
Fator de balanceamento
O fator de balanceamento/equilibrio de um nó T em uma
ABB é definido como:
14
Fator de balanceamento
O fator de balanceamento/equilibrio de um nó T em uma
ABB é definido como:
Para qualquer nó T em uma árvore AVL, o fator de
balanceamento assume o valor: +1, 0, -1.
O fator de balanceamento de uma folha?
15
Fator de balanceamento
16
Fator de balanceamento
Fator=0
Alturas das subárvores
esquerda e direita
são iguais
17
Fator de balanceamento
Fator=+1
Alturas da subárvore
esquerda é maior
18
Fator de balanceamento
Fator=-1
Alturas da subárvore
esquerda é menor
19
Exemplo: Inserção de 'Maio'
20
Exemplo: Inserção de 'Março'
21
Exemplo: Inserção de 'Março'
22
Exemplo: Inserção de 'Novembro'
23
Exemplo: Inserção de 'Novembro'
24
Exemplo: Inserção de 'Novembro'
25
Exemplo: Inserção de 'Agosto'
26
Exemplo: Inserção de 'Agosto'
27
Exemplo: Inserção de 'Abril'
28
Exemplo: Inserção de 'Abril'
29
Exemplo: Inserção de 'Abril'
30
Exemplo: Inserção de 'Janeiro'
31
Exemplo: Inserção de 'Janeiro'
32
Exemplo: Inserção de 'Janeiro'
33
Exemplo: Inserção de 'Dezembro'
34
Exemplo: Inserção de 'Dezembro'
35
Exemplo: Inserção de 'Julho'
36
Exemplo: Inserção de 'Julho'
37
Exemplo: Inserção de 'Fevereiro'
38
Exemplo: Inserção de 'Fevereiro'
39
Exemplo: Inserção de 'Fevereiro'
40
Exemplo: Inserção de 'Junho'
41
Exemplo: Inserção de 'Junho'
42
Exemplo: Inserção de 'Outubro'
43
Exemplo: Inserção de 'Outubro'
44
Exemplo: Inserção de 'Outubro'
45
Exemplo: Inserção de 'Setembro'
46
Exemplo: Inserção de 'Setembro'
47
Rotações
48
Rotações
O processo de rebalanceamento é conduzido utilizando 4
tipos de rotações
LL
RR
LR
RL
Suponha que o novo nó inserido é Y:
As rotações são caracterizadas pelo ancestral A (com fator
de balanceamento +2 ou -2) mais próximo do nó Y.
49
Rotações
LL: Y inserido na subárvore esquerda da subárvore esquerda de A
LR: Y inserido na subárvore direita da subárvore esquerda de A
RR: Y inserido na subárvore direita da subárvore direita de A
RL: Y inserido na subárvore esquerda da subárvore direita de A
Seja B o filho de A no qual ocorreu a inserção de Y
LL (A = +2; B = +1)
LR (A = +2; B = -1)
RR (A = -2; B = -1)
RL (A = -2; B = +1)
A
B
Y
50
Rotação LL
51
Rotação LL
52
Rotação LL
53
Rotação LL
54
Rotação LL
55
Rotação LL
56
Rotação LL
57
Rotação LL
58
Rotação RR
59
Rotação RR
60
Rotação RR
61
Rotação RR
62
Rotação RR
63
Rotação RR
64
Rotação RR
65
Rotação RR
66
Rotação LR (a)
67
Rotação LR (b)
68
Rotação LR (b)
69
Rotação LR (b)
70
Rotação LR (c)
71
Rotação LR (c)
72
Rotação LR (c)
73
Rotação LR
74
Rotação LR
75
Rotação LR
76
Rotação LR
77
Rotação LR
78
Rotação LR
79
Rotação LR
80
Rotação LR
81
Rotação RL (a)
82
Rotação RL (b)
83
Rotação RL (b)
84
Rotação RL (b)
85
Rotação RL (c)
86
Ferramenta de visualização: AVL
http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html
-1*(
)
87
Atividade em aula
Suponha que serão realizadas as seguintes inserções de
chaves na árvore AVL ao lado:
7
2
4
1
5
3
6
(a) Apresente a árvore AVL resultante (1 árvore)
(b) Indique o tipo de rotações consideradas em cada inserção
88
Atividade em aula
Operações
7 : RR
2 : -1 : LL
3 : LR
6 : RL
89
AVL é uma árvores balanceada?
90
Balanceamento de árvores AVL
Uma árvore AVL de altura h é balanceada se h = O(log(n))
Outra forma de pensar: Dada uma árvore AVL de altura h,
qual seria o valor mínimo possivel para n?
91
Balanceamento de árvores AVL
Uma árvore AVL de altura h é balanceada se h = O(log(n))
Outra forma de pensar: Dada uma árvore AVL de altura h,
qual seria o valor mínimo possivel para n?
h-2
h-1
92
Balanceamento de árvores AVL
Seja Th uma árvore AVL com altura h e número mínimo de
nós.
Nesta definição → h=4
T1
T2
T3
T4
93
Balanceamento de árvores AVL
Basta calcular um limite inferior do número de nós de Th.
Seja |Th| o número de nós de Th.
94
Analogia com a sequência de Fibonacci
95
AVL
Como
AVL é uma árvore balanceada!
Temos
96
AVL
Um teorema provado por Adelson-Velskii e Landis garante que a árvore
balanceada nunca será 45% mais alta que a correspondente árvore
perfeitamente balanceada, independentemente do número de nós existentes.
●
97
AVL
98
Para finalizar
Árvores balanceadas são muito utilizadas em problemas
reais:
JAVA: TreeMap, TreeSet.
C++: Map, Set do STL.
Custo de busca, inserção, remoção da árvore AVL: O(log n)
99
Sobre os slides
Slides baseados em:
Szwarcfiter, J.L. & Markezon, L. Estruturas de Dados e
seus Algoritmos, 3a edição, LTC, 2010.
Horowitz, E. & Sahni, S.; Fundamentos de Estruturas de
Dados, Editora Campus, 1984.
Wirth, N.; Algoritmos e Estruturas de Dados,
Prentice/Hall do Brasil, 1989.
Material de aula do Prof. José Augusto Baranauskas
(USP/Riberão Preto)
100