Árvores Binárias

Prévia do material em texto

Cloves Oliveira dos Santos 
ÁRVORES BINÁRIAS 
Universidade Federal de Alagoas – Campus Arapiraca 
Ciência da Computação – Laboratório de Programação 3 
Prof. Elthon Allex 
ROTEIRO 
2 
• Árvores; 
• Árvore ziguezague; 
• Árvore binária; 
• Árvore estritamente binária; 
• Árvore binária completa; 
• Árvore binária cheia. 
 
• Árvore AVL; 
• Problema; 
• Solução; 
• Árvore ziguezague; 
 
• Árvore binária; 
 
• Árvore estritamente binária; 
 
• Árvore binária completa; 
 
• Árvore binária cheia. 
ÁRVORES 
50 
31 
40 
42 
44 
43 
Grau < 2. 
3 
• Árvore ziguezague; 
 
• Árvore binária; 
 
• Árvore estritamente binária; 
 
• Árvore binária completa; 
 
• Árvore binária cheia. 
ÁRVORES 
20 50 
31 
40 
42 35 
44 
Grau <= 2. 
4 
• Árvore ziguezague; 
 
• Árvore binária; 
 
• Árvore estritamente binária; 
 
• Árvore binária completa; 
 
• Árvore binária cheia. 
ÁRVORES 
20 
60 
50 
31 
40 
42 35 
44 41 
Grau 0 ou 2. 
5 
• Árvore ziguezague; 
 
• Árvore binária; 
 
• Árvore estritamente binária; 
 
• Árvore binária completa; 
 
• Árvore binária cheia. 
ÁRVORES 
20 
31 
10 25 
43 
38 50 
38 50 
Sub-árvores vazias no ultimo 
ou penúltimo nível. 
Grau 0 ou 2. 
6 
• Árvore ziguezague; 
 
• Árvore binária; 
 
• Árvore estritamente binária; 
 
• Árvore binária completa; 
 
• Árvore binária cheia. 
ÁRVORES 
20 
31 
10 25 
43 
38 50 
Grau 2. 
Nós: 
2ℎ+1 − 1 
ℎ = 2 
𝑛𝑜𝑠 = 22+1 − 1 
𝑛𝑜𝑠 = 7 
7 
ÁRVORE AVL 
 
• AVL – Surgiu de seus criadores, Adelson Velsky e Landi; 
 
• Deixar a árvore com o menor número de níveis possível; 
 
• Balancear pela altura para melhorar a eficiência diminuindo o tempo de pesquisa; 
 
• As alturas das sub-árvores a partir de cada nó difere no máximo em uma unidade; 
 
8 
• AVL: • Não AVL: 
ÁRVORE AVL 
0 
0 
1 
0 
0 0 
0 
1 
0 
0 0 
0 
0 
0 
1 
0 
0 0 
0 
2 
0 0 
0 
2 
0 
3 
0 
1 
2 
0 2 
2 
0 0 
0 
1 
1 
1 1 
0 
0 
0 
Os números dentro dos nós é a diferença entre as alturas das sub-árvores da direita e esquerda. 
9 
ÁRVORE AVL – PROBLEMA 
• Implementação em C++. 
10 
ÁRVORE AVL – PROBLEMA 
• Testando... 
11 
ÁRVORE AVL – PROBLEMA 
0 
2 
1 
1 
0 
0 
1 
0 
1 
2 
3 
50 
17 76 
19 
54 9 23 
14 
12 
72 
67 
Há perda de desempenho. 
12 
ÁRVORE AVL – SOLUÇÃO 
• Balancear na inserção e remoção; 
 
• Variáveis ou outro meio para: 
• Fator de balanceamento (fb); 
• Nó direito; 
• Nó esquerdo; 
• Nó pai. 
 
• Usar rotação para balancear: 
• Rotação (LL): O novo nó X é inserido na sub-árvore da esquerda do filho esquerdo de A; 
• Rotação (LR): X é inserido na sub-árvore da direita do filho esquerdo de A; 
• Rotação (RR): X é inserido na sub-árvore da direita do filho direito de A; 
• Rotação (RL): X é inserido na sub-árvore da esquerda do filho direito de A. 
13 
ÁRVORE AVL – SOLUÇÃO 
 
• Inserção: 
• Inserção normal, como mostrado anteriormente; 
• Verificação do fator de balanceamento; 
• Se não estiver balanceado, usar rotação. 
 
• Remoção: 
• Usar rotação em torno do nó para torna-lo folha; 
• Pode necessitar realizar outras rotações para balancear a árvore. 
14 
ÁRVORE AVL – SOLUÇÃO 
 
• Fator de balanceamento: 
 
• Valor inicial 0; 
 
• Para estar balanceado -1 ≤ fb ≤ 1, valor diferente indica o não balanceamento; 
 
• A partir de um dado nó, usualmente 𝑓𝑏 = ℎ𝑒𝑠𝑞 − (ℎ𝑑𝑖𝑟). 
15 
 
• Rotação LL - rotação à direita: 
• Seja N2 o filho à esquerda de N1; 
 
• Inserindo um nó à esquerda do 
filho esquerdo de N1; 
 
• Torna o filho direito de N2 filho 
esquerdo de N1; 
 
• Torna N1 filho direito de N2. 
ÁRVORE AVL – SOLUÇÃO 
1 
0 
N1 
N2 
A1 A2 
A3 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
ℎ𝐴1 = 2 
ℎ𝐴2 = 2 
ℎ𝐴3 = 2 
Sub-árvore 16 
 
• Rotação LL: 
• Seja N2 o filho à esquerda de N1; 
 
• Inserindo um nó à esquerda do 
filho esquerdo de N1; 
 
• Torna o filho direito de N2 filho 
esquerdo de N1; 
 
• Torna N1 filho direito de N2. 
ÁRVORE AVL – SOLUÇÃO 
2 
1 
N1 
N2 
A1 A2 
A3 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
𝒉𝑨𝟏 = 𝟑 
ℎ𝐴2 = 2 
ℎ𝐴3 = 2 
Sub-árvore 17 
 
• Rotação LL: 
• Seja N2 o filho à esquerda de N1; 
 
• Inserindo um nó à esquerda do 
filho esquerdo de N1; 
 
• Torna o filho direito de N2 filho 
esquerdo de N1; 
 
• Torna N1 filho direito de N2. 
 
ÁRVORE AVL – SOLUÇÃO 
0 3 
N2 
A1 A2 A3 
N1 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
𝒉𝑨𝟏 = 𝟑 
ℎ𝐴2 = 2 
ℎ𝐴3 = 2 
Sub-árvore 18 
 
• Rotação LL: 
• Seja N2 o filho à esquerda de N1; 
 
• Inserindo um nó à esquerda do 
filho esquerdo de N1; 
 
• Torna o filho direito de N2 filho 
esquerdo de N1; 
 
• Torna N1 filho direito de N2. 
ÁRVORE AVL – SOLUÇÃO 
1 
N2 
A1 
0 
A2 A3 
N1 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
𝒉𝑨𝟏 = 𝟑 
ℎ𝐴2 = 2 
ℎ𝐴3 = 2 
Sub-árvore 19 
ÁRVORE AVL – SOLUÇÃO 
20 
1 
N2 
A1 
0 
A2 A3 
N1 
Sub-árvore 
Rotação LL: Comparando 
2 
1 
N1 
N2 
A1 A2 
A3 
Antes... Depois... 
 
• Rotação RR - rotação à esquerda: 
• Seja N2 o filho à direita de N1; 
 
• Inserindo um nó à direita do filho 
direito de N1; 
 
• Torna o filho esquerdo de N2 filho 
direito de N1; 
 
• Torna N1 filho esquerdo de N2. 
ÁRVORE AVL – SOLUÇÃO 
-1 
N1 
A1 
0 
A2 A3 
N2 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
ℎ𝐴1 = 2 
ℎ𝐴2 = 3 
ℎ𝐴3 = 3 
Sub-árvore 
Processo inverso 
21 
 
• Rotação RR: 
• Seja N2 o filho à direita de N1; 
 
• Inserindo um nó à direita do filho 
direito de N1; 
 
• Torna o filho esquerdo de N2 filho 
direito de N1; 
 
• Torna N1 filho esquerdo de N2. 
ÁRVORE AVL – SOLUÇÃO 
-2 
N1 
A1 
-1 
A2 A3 
N2 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
ℎ𝐴1 = 2 
ℎ𝐴2 = 3 
𝒉𝑨𝟑 = 𝟒 
Sub-árvore 
Processo inverso 
22 
 
• Rotação RR: 
• Seja N2 o filho à direita de N1; 
 
• Inserindo um nó à direita do filho 
direito de N1; 
 
• Torna o filho esquerdo de N2 filho 
direito de N1; 
 
• Torna N1 filho esquerdo de N2. 
ÁRVORE AVL – SOLUÇÃO 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
ℎ𝐴1 = 2 
ℎ𝐴2 = 3 
𝒉𝑨𝟑 = 𝟒 
Sub-árvore 
Processo inverso 
-4 
A3 
N2 
-1 
N1 
A1 A2 
23 
 
• Rotação RR: 
• Seja N2 o filho à direita de N1; 
 
• Inserindo um nó à direita do filho 
direito de N1; 
 
• Torna o filho esquerdo de N2 filho 
direito de N1; 
 
• Torna N1 filho esquerdo de N2. 
ÁRVORE AVL – SOLUÇÃO 
𝑓𝑏 = 𝑒𝑠𝑞 − 𝑑𝑖𝑟 
ℎ𝐴1 = 2 
ℎ𝐴2 = 3 
𝒉𝑨𝟑 = 𝟒 
Sub-árvore 
Processo inverso 
-1 
-1 
N2 
N1 
A1 A2 
A3 
24 
ÁRVORE AVL – SOLUÇÃO 
25 Sub-árvore 
Rotação RR: Comparando 
Antes... Depois... 
-1 
-1 
N2 
N1 
A1 A2 
A3 
-2 
N1 
A1 
-1 
A2 A3 
N2 
 
• Rotação LR - rotação dupla à direita: 
• Seja N2 o filho à esquerda de N1 
e o N3 filho à direita de N2; 
 
• Inserindo um nó à direita do filho 
esquerdo de N1; 
 
• Executa Rotação RR em N2 e 
N3; 
 
• Executa Rotação LL em N1 e N3. 
ÁRVORE AVL – SOLUÇÃO 
ℎ𝐴1 = 1 
ℎ𝐴2 = 0 
ℎ𝐴3 = 0 
ℎ𝐴4 = 1 
Sub-árvore 
0 
1 
0 
N1 
N2 
A1 
A4 
N3 
A2 A3 
26 
 
• Rotação LR: 
• Seja N2 o filho à esquerda de N1 
e o N3 filho à direitade N2; 
 
• Inserindo um nó à direita do filho 
esquerdo de N1; 
 
• Executa Rotação RR em N2 e 
N3; 
 
• Executa Rotação LL em N1 e N3. 
ÁRVORE AVL – SOLUÇÃO 
Sub-árvore 
1 
2 
-1 
N1 
N2 
A1 
A4 
N3 
A2 A3 
ℎ𝐴1 = 1 
𝒉𝑨𝟐 = 𝟏 
ℎ𝐴3 = 0 
ℎ𝐴4 = 1 
27 
 
• Rotação LR: 
• Seja N2 o filho à esquerda de N1 
e o N3 filho à direita de N2; 
 
• Inserindo um nó à direita do filho 
esquerdo de N1; 
 
• Executa Rotação RR em N2 e 
N3; 
 
• Executa Rotação LL em N1 e N3. 
ÁRVORE AVL – SOLUÇÃO 
Sub-árvore 
1 
N3 
A3 
0 
N2 
A1 A2 
2 
N1 
A4 
ℎ𝐴1 = 1 
𝒉𝑨𝟐 = 𝟏 
ℎ𝐴3 = 0 
ℎ𝐴4 = 1 
28 
 
• Rotação LR: 
• Seja N2 o filho à esquerda de N1 
e o N3 filho à direita de N2; 
 
• Inserindo um nó à direita do filho 
esquerdo de N1; 
 
• Executa Rotação RR em N2 e 
N3; 
 
• Executa Rotação LL em N1 e N3. 
ÁRVORE AVL – SOLUÇÃO 
Sub-árvore 
-1 1 0 
N2 
A1 A2 A3 
0 
N3 
A4 
N1 
ℎ𝐴1 = 1 
𝒉𝑨𝟐 = 𝟏 
ℎ𝐴3 = 0 
ℎ𝐴4 = 1 
29 
ÁRVORE AVL – SOLUÇÃO 
30 Sub-árvore 
Rotação LR: Comparando 
Antes... Depois... 
-1 1 0 
N2 
A1 A2 A3 
0 
N3 
A4 
N1 
1 
2 
-1 
N1 
N2 
A1 
A4 
N3 
A2 A3 
ÁRVORE AVL – SOLUÇÃO 
31 
 
• Rotação RL - rotação dupla à esquerda: 
• Exatamente o contrário da rotação LR; 
 
• Executa Rotação LL; 
 
• Em seguida executa Rotação RR; 
 
• Posteriormente será mostrado o estado antes da rotação e o final; 
ÁRVORE AVL – SOLUÇÃO 
32 Sub-árvore 
Rotação RL: Comparando 
Antes... Depois... 
-1 1 0 
N2 
A4 A3 A2 
0 
N3 
A1 
N1 
1 
-2 
1 
N1 
N2 
A4 
A1 
N3 
A3 A2 
ÁRVORE AVL – SOLUÇÃO 
0 
50 
Inserção: 
50 → raiz 
Resolvendo o exemplo testado em C++... 
33 
ÁRVORE AVL – SOLUÇÃO 
0 
1 
50 
17 
Inserção: 
50 → raiz; 
50: esq = 17 
34 
ÁRVORE AVL – SOLUÇÃO 
0 
0 
0 
50 
17 76 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76 
35 
ÁRVORE AVL – SOLUÇÃO 
0 
1 
1 
0 
50 
17 76 
9 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9 
36 
ÁRVORE AVL – SOLUÇÃO 
0 0 
0 
1 
0 
50 
17 76 
9 23 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9; 
17: dir = 23 
37 
ÁRVORE AVL – SOLUÇÃO 
0 0 
0 
0 
0 
1 
50 
17 76 
54 9 23 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9; 
17: dir = 23; 
76: esq = 54 
38 
ÁRVORE AVL – SOLUÇÃO 
-1 
0 
0 
1 
1 
0 
1 
50 
17 76 
54 9 23 
14 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9; 
17: dir = 23; 
76: esq = 54; 
9: dir = 14 
39 
ÁRVORE AVL – SOLUÇÃO 
-1 
0 
1 
0 
0 
1 
0 
1 
50 
17 76 
19 
54 9 23 
14 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9; 
17: dir = 23; 
76: esq = 54; 
9: dir = 14; 
23: esq = 19 
40 
ÁRVORE AVL – SOLUÇÃO 
-1 
0 
1 
0 
0 
0 
0 
-1 
2 
50 
17 76 
19 
54 9 23 
14 72 
Inserção: 
50 → raiz; 
50: esq = 17; 
50: dir = 76; 
17: esq = 9; 
17: dir = 23; 
76: esq = 54; 
9: dir = 14; 
23: esq = 19; 
54: dir = 72 
Aplica rotação LR → Rotação RR seguida de LL. 
41 
ÁRVORE AVL – SOLUÇÃO 
Inserção: 
50 → raiz; 
50: esq = 17; 
72: dir = 76; 
17: esq = 9; 
17: dir = 23; 
72: esq = 54; 
9: dir = 14; 
23: esq = 19; 
50: dir = 72 
-1 
0 
1 
0 
0 
0 
-1 
0 
50 
17 72 
19 
54 9 23 
14 
0 
76 
Resultado... 
42 
ÁRVORE AVL – SOLUÇÃO 
-2 
1 
1 
0 
1 
1 
-1 
0 
50 
17 72 
19 
54 9 23 
14 
0 
76 
Inserção: 
50 → raiz; 
50: esq = 17; 
72: dir = 76; 
17: esq = 9; 
17: dir = 23; 
72: esq = 54; 
9: dir = 14; 
23: esq = 19; 
50: dir = 72; 
14: esq = 12 0 
12 
Aplica rotação RL → Rotação LL seguida de RR. 
43 
ÁRVORE AVL – SOLUÇÃO 
Inserção: 
50 → raiz; 
50: esq = 17; 
72: dir = 76; 
12: esq = 9; 
17: dir = 23; 
72: esq = 54; 
12: dir = 14; 
23: esq = 19; 
50: dir = 72; 
17: esq = 12 
Resultado... 
1 
0 
0 
1 
-1 
0 
50 
17 72 
19 
54 23 
0 
76 
0 
0 
0 
12 
14 9 
44 
ÁRVORE AVL – SOLUÇÃO 
Inserção: 
50 → raiz; 
50: esq = 17; 
72: dir = 76; 
12: esq = 9; 
17: dir = 23; 
72: esq = 54; 
12: dir = 14; 
23: esq = 19; 
50: dir = 72; 
17: esq = 12; 
54: dir = 67. 
Resultado final... 
1 
0 
0 
0 
-1 
1 
50 
17 72 
19 
54 23 
0 
76 
0 
0 
0 
12 
14 9 
0 
67 
45 
ÁRVORE AVL – SOLUÇÃO 
46 
• Novas Implementações: 
 
ÁRVORE AVL – SOLUÇÃO 
47 
• Novas 
Implementações: 
ÁRVORE AVL – SOLUÇÃO 
48 
• Novas Implementações: 
ÁRVORE AVL – SOLUÇÃO 
49 
• Novas Implementações: 
raiz: 50 
50: dir = 72 
72: dir = 76 
72: esq = 54 
54: dir = 67 
50: esq = 17 
17: dir = 23 
23: esq = 19 
17: esq = 12 
12: dir = 14 
12: esq = 9 
 
AVL? 
(0 - false, 1 - true): 1 
FONTES 
 
• http://www.inf.ufrgs.br/~galante/wiki/lib/exe/fetch.php?id=inf01203&cache=cache&media=i
nf01203-arvbinarias.pdf 
• http://www.mat.uc.pt/~amca/ED0506/Acet1.6.pdf 
• http://d.yimg.com/kq/groups/23650627/855905455/name/arvores-binarias.pdf 
• http://pt.wikipedia.org/wiki/%C3%81rvore_AVL 
• http://www.lcad.icmc.usp.br/~nonato/ED/AVL/node67.html 
• http://www.lcad.icmc.usp.br/~nonato/ED/AVL/insercao.html 
• http://www.youtube.com/watch?v=mKMwi691rs8 
• http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html 
50 
51