Upload
dangdat
View
216
Download
0
Embed Size (px)
Citation preview
1
Aula 10 – Árvores Adelson-Velskii e Landis
MC3305Algoritmos e Estruturas de Dados II
Prof. Jesús P. [email protected]
2Q-2014
2
Árvores balanceadas
3
Á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.
4
Árvores balanceadas
Exemplo ruim para o restabablecimento de árvores completas
Fonte: SZWARCFITER, J. L.; MARKEZON, L. Estruturas de Dados e seus Algoritmos, 3a edição, LTC, 2010.
Para obter esta árvore é necessário percorrer toda a árvore, O(n)
5
Árvores balanceadas: completas e AVLs
6
AVL
Georgy M. Adelson-VelskyRussia
(1922-2014/abril/26)
Evgenii Mikhailovich Landis Ucrania
(1921-1997)
7
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.
8
Árvores AVL
Devido ao balanceamento da altura da árvore, as operações de:
BuscaInserçãoRemoção
em uma árvore com n elementos podem ser efetuadas em mesmo no pior caso.
9
Árvores AVL
Devido ao balanceamento da altura da árvore, as operações de:
BuscaInserçãoRemoçã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.
10
Árvores AVL
Uma árvore AVL é definida como:Uma árvore vazia é uma árvore AVL.
11
Árvores AVL
Uma árvore AVL é definida como:Uma árvore vazia é uma árvore AVL.Sendo T uma ABB, com subárvores esquerda (L) edireita (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.
12
Árvores AVL
13
Fator de balanceamento
14
Fator de balanceamento
O fator de balanceamento/equilibrio de um nó T em uma ABB é definido como:
15
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?
16
Fator de balanceamento
17
Fator de balanceamento
Fator=0Alturas das subárvores
esquerda e direitasão iguais
18
Fator de balanceamento
Fator=+1Alturas da subárvore
esquerda é maior
19
Fator de balanceamento
Fator=-1Alturas da subárvore
esquerda é menor
20
Exemplo: Inserção de 'Maio'
21
Exemplo: Inserção de 'Março'
22
Exemplo: Inserção de 'Março'
23
Exemplo: Inserção de 'Novembro'
24
Exemplo: Inserção de 'Novembro'
25
Exemplo: Inserção de 'Novembro'
26
Exemplo: Inserção de 'Agosto'
27
Exemplo: Inserção de 'Agosto'
28
Exemplo: Inserção de 'Abril'
29
Exemplo: Inserção de 'Abril'
30
Exemplo: Inserção de 'Abril'
31
Exemplo: Inserção de 'Janeiro'
32
Exemplo: Inserção de 'Janeiro'
33
Exemplo: Inserção de 'Janeiro'
34
Exemplo: Inserção de 'Dezembro'
35
Exemplo: Inserção de 'Dezembro'
36
Exemplo: Inserção de 'Julho'
37
Exemplo: Inserção de 'Julho'
38
Exemplo: Inserção de 'Fevereiro'
39
Exemplo: Inserção de 'Fevereiro'
40
Exemplo: Inserção de 'Fevereiro'
41
Exemplo: Inserção de 'Junho'
42
Exemplo: Inserção de 'Junho'
43
Exemplo: Inserção de 'Outubro'
44
Exemplo: Inserção de 'Outubro'
45
Exemplo: Inserção de 'Outubro'
46
Exemplo: Inserção de 'Setembro'
47
Exemplo: Inserção de 'Setembro'
48
Rotações
49
Rotações
O processo de rebalanceamento é conduzido utilizando 4 tipos de rotações
LLRRLRRL
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.
50
Rotações
LL: Y inserido na subárvore esquerda da subárvore esquerda de ALR: Y inserido na subárvore direita da subárvore esquerda de ARR: Y inserido na subárvore direita da subárvore direita de ARL: 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 YLL (A = +2; B = +1)LR (A = +2; B = -1)RR (A = -2; B = -1)RL (A = -2; B = +1)
A
B
Y
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 LL
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 RR
67
Rotação LR (a)
68
Rotação LR (b)
69
Rotação LR (b)
70
Rotação LR (b)
71
Rotação LR (c)
72
Rotação LR (c)
73
Rotação LR (c)
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 LR
82
Rotação RL (a)
83
Rotação RL (b)
84
Rotação RL (b)
85
Rotação RL (b)
86
Rotação RL (c)
87
Ferramenta de visualização: AVL
http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html
-1*( )
88
Atividade em aula
Suponha que serão realizadas as seguintes inserções de chaves na árvore AVL ao lado:
72136
(a) Apresente a árvore AVL resultante (1 árvore)(b) Indique o tipo de rotações consideradas em cada inserção
4
5
89
Atividade em aula
Operações
7 : RR2 : --1 : LL3 : LR6 : RL
90
AVL é uma árvores balanceada?
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?
92
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-1
h-2
93
Balanceamento de árvores AVL
Seja Th uma árvore AVL com altura h e número mínimo de nós.
T1 T2 T3 T4
Nesta definição → h=4
94
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.
95
Analogia com a sequência de Fibonacci
96
AVL
AVL é uma árvore balanceada!
Como Temos
97
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.
98
AVL
99
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)
100
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)