Estruturas de Dados - Busca (Alexandre)

Prévia do material em texto

Estrutura de DadosEstrutura de Dados
EstruturaEstrutura de Dadosde Dados
DisciplinaDisciplina 116319116319
Prof. Alexandre ZaghettoProf. Alexandre ZaghettoProf. Alexandre ZaghettoProf. Alexandre Zaghetto
zaghetto@gmail.comzaghetto@gmail.com
UniversidadeUniversidade de Brasíliade Brasília
InstitutoInstituto de de CiênciasCiências ExatasExatas
DepartamentoDepartamento de de CiênciaCiência dada ComputaçãoComputação
Estrutura de DadosEstrutura de Dados
BuscaBusca
(ou Pesquisa)(ou Pesquisa)(ou Pesquisa)(ou Pesquisa)
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Consiste na verificação da existência de um valor dentro
de um conjunto de dados.
• Trataremos da pesquisa seqüencial
19/08/201019/08/2010 33
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Uma vez que os elementos não estão ordenados por
algum critério, o método mais simples de se pesquisar
um elemento é a pesquisa seqüencial ou linear.
� Verificamos seqüencialmente, ou seja, um após o
outro, se o elemento desejado se encontra no conjunto.
19/08/201019/08/2010 44
outro, se o elemento desejado se encontra no conjunto.
� Caso isso ocorra, então a pesquisa foi bem-
sucedida.
� Caso todos os elementos do conjunto sejam
verificados e o elemento desejado não esteja dentre
eles, dizemos que a pesquisa foi mal-sucedida.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Podemos perceber facilmente que quanto maior o
vetor, menos eficaz a pesquisa seqüencial se torna.
� No pior dos casos teremos que pesquisar todos os n
elementos, e na média, teremos que pesquisar pelo
menos a metade deles para encontrar o elemento
19/08/201019/08/2010 55
menos a metade deles para encontrar o elemento
desejado.
� Na média percorreremos até a metade do vetor (n/2).
� Eficiência: pior caso � , caso médio � .)(nO )(nO
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Implementação em C:
int busca (int* vet, int n, int elem){
int i;
19/08/201019/08/2010 66
for (i=0; i<n; i++) {
if (elem == vet[i])
return i;
}
return -1;
}
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Se assumimos que os elementos estão armazenados
em ordem crescente, podemos concluir que um elemento
não está no vetor tão logo o primeiro valor maior é
encontrado.
19/08/201019/08/2010 77
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Implementação em C:
int busca_ord (int n, int* vet, int elem){
int i;
19/08/201019/08/2010 88
for (i=0; i<n; i++) {
if (elem == vet[i])
return i
else if (elem < vet[i])
return -1;
}
return -1;
}
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca seqüencial (ou linear):
� Se assumimos que os elementos estão armazenados
em ordem crescente, podemos concluir que um elemento
não está no vetor tão logo o primeiro valor maior é
encontrado.
� A complexidade, porém, não é reduzida quando o
19/08/201019/08/2010 99
� A complexidade, porém, não é reduzida quando o
número de elementos é muito grande.
� Se o vetor está ordenado, existe um algoritmo muito
mais eficiente que será apresentado a seguir.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� O algoritmo inicialmente deve verificar o valor do
elemento que está no “meio” do vetor.
� Se este elemento (do meio) for maior que o valor
procurado, deve-se restringir a busca à primeira metade
do vetor.
19/08/201019/08/2010 1010
do vetor.
� Caso contrário, deve-se restringir a busca à segunda
metade do vetor.
� Esse procedimento é repetido até que o elemento seja
encontrado ou que não haja mais elementos a testar.
� Eficiência: pior caso � , caso médio �)(log2 nO ).(log2 nO
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1111
16 18 20 22 24 26 28
24 26 28
24
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1212
16 18 20 22 24 26 28
24 26 28
24
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1313
16 18 20 22 24 26 28
24 26 28
24
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1414
16 18 20 22 24 26 28
24 26 28
24
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1515
16 18 20 22 24 26 28
24 26 28
24
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1616
0 2 4 6 8 10 12
8 10 12
8
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1717
0 2 4 6 8 10 12
8 10 12
8
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1818
0 2 4 6 8 10 12
8 10 12
8
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 1919
0 2 4 6 8 10 12
8 10 12
8
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Exemplos:
Valor de Pesquisa: 8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
19/08/201019/08/2010 2020
0 2 4 6 8 10 12
8 10 12
8
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Implementação em C:
int busca_bin (int* vet, int n, int elem){
int ini = 0, fim = n-1, meio;
while (ini <= fim) {
19/08/201019/08/2010 2121
while (ini <= fim) {
meio = (ini + fim) / 2;
if (elem < vet[meio])
fim = meio – 1;
else if (elem > vet[meio])
ini = meio + 1;
else
return meio;
}
return -1;
}
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Implementação recursiva em C (não retorna o índice do
elemento, apenas indica se encontrou ou não):
int busca_bin_rec (int* vet, int n, int elem){
if (n <= 0) return 0;
19/08/201019/08/2010 2222
if (n <= 0) return 0;
else {
int meio = (n - 1) / 2;
if (elem < vet[meio])
return busca_bin_rec(vet, meio, elem);
else if (elem > vet[meio])
return busca_bin_rec(&vet[meio+1], n–1-meio, elem);
else
return 1;
}
}
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca binária:
� Implementação recursiva em C (retorna o índice do
elemento):
int busca_bin_rec (int* vet, int n, int elem){
if (n <= 0) return -1;
else {
19/08/201019/08/2010 2323
else {
int meio = (n - 1) / 2;
if (elem < vet[meio])
return busca_bin_rec(vet, meio, elem);
else if (elem > vet[meio]) {
int r = busca_bin_rec(&vet[meio+1],n-1-meio, elem);
if (r<0) return -1;
else return meio+1+r;
} else {
return meio;
}
}
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Já vimos nas aulas sobre árvores binárias.
� Exemplo: 14 15 4 9 7 18 3 5 16 4 20 17 9 14 5.
14
19/08/201019/08/2010 2424
154
9
7
183
2016
175
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Para que seja possível usar árvores binárias de
busca mantendo sempre a altura das árvores no
mínimo, ou próximo dele, é necessário um processo
para gerar árvores binárias balanceadas.
� Uma árvore binária balanceada é uma árvore
19/08/201019/08/2010 2525
� Uma árvore binária balanceada é uma árvore
binárias na qual as profundidades das duas
subárvores de todo nó nunca diferem em mais de
1.
� Uma árvore binária AVL (Adelson, Velsky e
Landis) é uma árvore binária de busca auto-
balanceada.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore binária não balanceada: 2, 1,
3, 4, 5, 6, 7, 8, 9.
2
31
4
19/08/201019/08/2010 2626
4
5
6
7
8
9
Se desejamos inserir o valor
10, teremos que realizar
comparações de 2 a 9!
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore binária balanceada: 2, 1, 3, 4,
5, 6, 7, 8, 9.
5
83
19/08/201019/08/2010 2727
83
2
1
6 9
7
Se desejamos inserir o valor
10, teremos que realizar
comparações com o 5, 8 e
9.
4
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore binária balanceada:
Fator de balanceamento (FB):
diferença entre as profundidades
das subárvores esquerda e direita.
19/08/201019/08/2010 2828
3
4
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore binária balanceada:
19/08/201019/08/2010 2929
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� É fácil verificar que a árvore se torna desbalanceada
apenas se o nó recém-inserido é um descendente
esquerdo de um nó que tinha anteriormente um
balanceamento 1.
19/08/201019/08/2010 3030
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Ou se o nó recém-inserido é um descendente
direito de um nó que tinha anteriormente um
balanceamento -1.
19/08/201019/08/2010 3131
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Os ancestrais mais jovem que se tornam
desbalanceados em cada nova inserção são indicados
abaixo.
19/08/201019/08/2010 3232
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Para manter uma árvore balanceada a cada nova
inserção, é necessário fazer uma transformação, tal
que:
1. o percurso em ordem da árvore transformada seja
o mesmo da árvore original (garante que a árvore
19/08/201019/08/2010 3333
o mesmo da árvore original (garante que a árvore
continue sendo uma árvore de busca binária); e
2. a árvore transformada fique balanceada.
� A seguir vamos definir as operações rotationright
e rotationleft que realizam transformações com as
propriedades acima.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
19/08/201019/08/2010 3434
-3-2
2
1
10
0-1
00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
19/08/201019/08/2010 3535
-3-2
2
1
10
0-1
00
q
p
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
right(father(p)) = q;
19/08/201019/08/2010 3636
-3-2
2
1
10
0-1
00
q
p
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
right(father(p)) = q;
h = right(q);
19/08/201019/08/2010 3737
-3-2
2
1
10
0-1
00
q
p
NULL
h
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
right(father(p)) = q;
h = right(q);
right(q) = p;
19/08/201019/08/2010 3838
-3-2
2
1
10
0-1
00
right(q) = p;
q
p
h
NULL
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
right(father(p)) = q;
h = right(q);
right(q) = p;
19/08/201019/08/2010 3939
-3-2
2
1
10
0-1
00
right(q) = p;
left(p) = h;
q
p
h
NULL
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
0
q = left(p);
right(father(p)) = q;
h = right(q);
right(q) = p;
19/08/201019/08/2010 4040
-3-2
2
1
1
0
0-1
0
0
right(q) = p;
left(p) = h;
q p
h
NULL
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
�rightrotation(p): aumenta a profundidade da
subárvore à direita, diminuindo a profundidade da
subárvore à esquerda.
-1
q = left(p);
right(father(p)) = q;
h = right(q);
right(q) = p;
19/08/201019/08/2010 4141
-3-1
0
0
1
0
0-1
0
0
right(q) = p;
left(p) = h;
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
19/08/201019/08/2010 4242
-3-1
0
0
1
0
0-1
0
0
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
-3
q = right(p);
p
19/08/201019/08/2010 4343
-3-1
0
0
10
0-1
0
0
q
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
-3
q = right(p);
left(father(p)) = q;p
19/08/201019/08/2010 4444
-3-1
0
0
10
0-1
0
0
q
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
-3
q = right(p);
left(father(p)) = q;
h = left(q);
p
19/08/201019/08/2010 4545
-3-1
0
0
10
0-1
0
0
q
h
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
-3
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
p
19/08/201019/08/20104646
-3-1
0
0
10
0-1
0
0
left(q) = p;
q
h
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
-3
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
p
19/08/201019/08/2010 4747
-3-1
0
0
10
0-1
0
0
left(q) = p;
right(p) = h;
q
h
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
q
19/08/201019/08/2010 4848
-1
0
0
1
0
0
-1
0
0
left(q) = p;
right(p) = h;
-2
p
h
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
19/08/201019/08/2010 4949
-1
0
0
1
0
0
-1
0
0
-2
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
19/08/201019/08/2010 5050
-1
0
0
1
0
0
-1
0
0
-2
p
q
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
19/08/201019/08/2010 5151
-1
0
0
1
0
0
-1
0
0
-2
p
q
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
h = left(q);
19/08/201019/08/2010 5252
-1
0
0
1
0
0
-1
0
0
-2
p
q
NULLh
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
19/08/201019/08/2010 5353
-1
0
0
1
0
0
-1
0
0
-2
left(q) = p;
p
q
NULLh
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
19/08/201019/08/2010 5454
-1
0
0
1
0
0
-1
0
0
-2
left(q) = p;
right(p) = h;
p
q
NULLh
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
-1
1
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
19/08/201019/08/2010 5555
-1
0
0
1
0
0-1
00 -2
left(q) = p;
right(p) = h;
p
q
NULLh
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
0
1
q = right(p);
left(father(p)) = q;
h = left(q);
left(q) = p;
19/08/201019/08/2010 5656
-1
0
0
1
0
00
00 0
left(q) = p;
right(p) = h;
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� leftrotation(p): aumenta a profundidade da
subárvore à esquerda, diminuindo a profundidade da
subárvore à direita.
14
4
18
19/08/201019/08/2010 5757
� Observe que apesar das rotações, a árvore
continua sendo uma árvore binária de busca: o
filho esquerdo é menor e o filho direito é maior que o
pai.
4
9
7
3
2016
175 15
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Ao inserir ou remover elementos, a árvore terá de
ser verificada para que, caso necessário, seja feito um
rebalanceamento por meio de rotações.
19/08/201019/08/2010 5858
leftrotation(p)
rightrotation(p)
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
6 2
19/08/201019/08/2010 5959
3
74
2 5
0
01
-1 0
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
6 2
Árvore desbalanceada
FBs positivos.
19/08/201019/08/2010 6060
3
74
2 5
0
01
-1 0
Uma rotação simples
à direita resolve.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
6 4
19/08/201019/08/2010 6161
3
74
2 5 3
62
5 7
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
40
Árvore rebalanceada.
19/08/201019/08/2010 6262
3
62
5 70
0-1
0 0
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
5 -2
19/08/201019/08/2010 6363
8
3 7
96
0
0 -1
10
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
5 -2
Árvore desbalanceada
FBs negativos.
19/08/201019/08/2010 6464
8
3 7
96
0
0 -1
10
Uma rotação simples
à esquerda resolve.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
5 7
19/08/201019/08/2010 6565
8
3 7
96 8
5 9
63
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Entendendo as rotações:
70
Árvore rebalanceada.
19/08/201019/08/2010 6666
8
5 9
630
0 1
00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Mas nem sempre apenas uma rotação é suficiente
para balancear a árvore.
7 2
19/08/201019/08/2010 6767
3 8
52
4 6
-1 0
00
0 0
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
7 2
19/08/201019/08/2010 6868
3 8
52
4 6
-1 0
00
0 0
Árvore desbalanceada: FB pai
positivo e FB filho negativo.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
7 2
19/08/201019/08/2010 6969
3 8
52
4 6
-1 0
00
0 0
Será necessária uma rotação
dupla à direita.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
7 2
19/08/201019/08/2010 7070
3 8
52
4 6
-1 0
00
0 0
Será necessária uma rotação
dupla à direita.
Consiste em uma rotação
simples à esquerda no filho.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrênciade
uma rotação dupla.
7 7
19/08/201019/08/2010 7171
3 8
52
4 6
5
8
63
42
Será necessária uma rotação
dupla à direita.
Consiste em uma rotação
simples à esquerda no filho.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
7 7
19/08/201019/08/2010 7272
3 8
52
4 6
5
8
63
42
Será necessária uma rotação
dupla à direita.
Seguida de uma rotação
simples à direita no pai.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
7
19/08/201019/08/2010 7373
5
8
63
42
7
5
86
3
42
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
19/08/201019/08/2010 7474
7
5
86
3
42
0
0
00
0
00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
5 -2
19/08/201019/08/2010 7575
103
8 13
96
10
0 0
00
Árvore desbalanceada: FB pai
negativo e FB filho positivo.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
5 -2
19/08/201019/08/2010 7676
Será necessária uma rotação
dupla à esquerda.
103
8 13
96
10
0 0
00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
5 -2
19/08/201019/08/2010 7777
Consiste em uma rotação
simples à direita no filho.
Será necessária uma rotação
dupla à esquerda.
103
8 13
96
10
0 0
00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
5 5
19/08/201019/08/2010 7878
Consiste em uma rotação
simples à direita no filho.
Será necessária uma rotação
dupla à esquerda.
103
8 13
96
8
3
6 10
9 13
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
55
19/08/201019/08/2010 7979
Será necessária uma rotação
dupla à esquerda.
Seguida de uma rotação
simples à esquerda no pai.
8
3
6 10
9 13
103
8 13
96
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
5
19/08/201019/08/2010 8080
10
8
139
5
63
8
3
6 10
9 13
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Se um nó estiver desbalanceado e seu filho estiver
inclinado no sentido inverso, teremos a ocorrência de
uma rotação dupla.
19/08/201019/08/2010 8181
0
0
00
0
00
10
8
139
5
63
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5,
5 0
19/08/201019/08/2010 8282
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3
3
5 1
0
19/08/201019/08/2010 8383
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7
3
5 0
07 0
19/08/201019/08/2010 8484
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10
3
5 -1
07 -1
19/08/201019/08/2010 8585
10 10
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33
3
5 -2
07 -2
19/08/201019/08/2010 8686
10 -1
33
0
Árvore desbalanceada com FBs negativos.
Rotação simples à esquerda no nó desbalanceado mais jovem.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33
3
5 -1
010 0
19/08/201019/08/2010 8787
337 00
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33, 15
3
5 -2
010 -1
19/08/201019/08/2010 8888
337 0
15 0
1
Árvore desbalanceada com FBs negativos.
Rotação simples à esquerda no nó desbalanceado mais jovem.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33, 15
5
10 0
33 0 1
19/08/201019/08/2010 8989
153 7 00 0
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33, 15,
17.
5
10 -1
33 0 2
19/08/201019/08/2010 9090
153 7 -10 0
17 17
Árvore desbalanceada: FB pai positivo e FB filho negativo.
Rotação dupla à direita a partir do nó desbalanceado mais jovem.
Estrutura de DadosEstrutura de Dados
1. Busca1. Busca
• Busca em Árvores Binárias:
� Exemplo de árvore AVL: insere 5, 3, 7, 10, 33, 15,
17.
5
10 0
17 0 0
19/08/201019/08/2010 9191
� Eficiência: pior caso � , caso médio �
153 7 00 033 0
)(log2 nO ).(log2 nO