06.ED.ÁrvoresBuscaBinaria-2014-1

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Árvore Binária de Busca 
 
 Propriedade fundamental da árvore binária de 
busca 
 Valor da chave da raiz é: 
 Maior do que o valor da chave da subárvore da esquerda 
(SAE) 
 Menor do que o valor da chave da subárvore da direita 
(SAD) 
 A subárvore da esquerda e subárvore da direita 
obedecem à propriedade fundamental 
Árvore Binária de Busca 
2 
 Esquematicamente: 
Árvore Binária de Busca 
3 
Todos < x Todos  x 
x 
 O TAD TArvBin visto na aula de Árvores 
Binárias pode ser aproveitado, juntamente 
com suas operações 
 Algumas operações, entretanto, são interessantes 
de se repensar: 
 Busca 
 Inserção  substituindo a operação Cria 
 Remoção 
 Essas operações exploram a propriedade de 
ordenação das árvores binárias de busca. 
 Assim, o TAD TArvBinBusca poderia ser: 
Árvore Binária de Busca 
4 
Árvores Binárias 
5 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 
 No* Libera(No *p); 
 public: 
 TArvBinBusca(); 
 char ConsultaRaiz(); 
 ... 
 bool Vazia(); 
 bool Busca(char C); // chama operação AuxBusca 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
Árvores Binárias 
6 
 MI do TAD TArvBinBusca: 
 Operação Busca: 
Relembrando: como o parâmentro raiz da operação 
AuxBusca é um ponteiro, essa operação deve ser 
necessariamente privada. O TAB TArvBinBusca fica: 
bool TArvBinBusca::Busca(char C) 
{ 
 return AuxBusca(raiz, C); 
} 
Árvores Binárias 
7 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 bool AuxBusca(No *p, char C); // busca C na árvore 
 ... 
 
 No* Libera(No *p); 
 public: 
 TArvBinBusca(); 
 char ConsultaRaiz(); 
 ... 
 bool Vazia(); 
 bool Busca(char C); // chama operador AuxBusca 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
 O procedimento AuxBusca abaixo é a que foi 
apresentada para o TAD TArvBin e trabalha com 
uma árvore binária genérica. 
Busca em árvore binária genérica 
8 
bool TArvBin::AuxBusca(No *p, char C) 
{ 
 if (p == NULL) 
 return false; 
 else if (p->consultaInfo() == C) 
 return true; 
 else if (AuxBusca(p->consultaEsq(),C)) 
 return true; 
 else 
 return AuxBusca(p->consultaDir(),C); 
} 
 Então, a implementação da operação AuxBusca 
pode considerar a seguinte busca “simplificada”: 
 Compara-se o valor procurado com a informação do 
nó raiz: 
 Se igual, achou 
 Se menor, então buscar na subárvore da esquerda 
(SAE) 
 Se maior, então buscar na subárvore da direita (SAD) 
Árvore Binária de Busca 
9 
 Mas, na árvore binária de busca, pode-se 
modificar o procedimento AuxBusca original para 
levar em consideração a propriedade de 
ordenação. 
Busca em árvore binária de busca 
10 
bool TArvBinBusca::AuxBusca(No *p, char C) 
{ 
 if (p == NULL) 
 return false; 
 else if (p->consultaInfo() == C) 
 return true; 
 else if (C < p->consultaInfo()) 
 return AuxBusca(p->consultaEsq, C); 
 else 
 return AuxBusca(p->consultaDir(), C); 
} 
 Operação AuxBusca específica para uma árvore 
binária de busca: 
Exemplo: Busca 
11 
Qual o caminho percorrido para a chave 6? 
Qual o caminho percorrido para buscar a chave 4? 
2 
NULL 1 NULL 5 
NULL 3 NULL NULL NULL 6 
 A partir da árvore binária a seguir, apresentar os 
caminhos percorridos para buscar as chaves: 
 18 
 9 
 33 
 35 
 7 
Exercício - Busca 
12 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
 A partir da árvore binária a seguir, apresentar os 
caminhos percorridos para buscar as chaves: 
 18 
 9 
 33 
 35 
 7 
Exercício - Busca 
13 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
 Complexidade: o número de comparações é proporcional à 
altura h da árvore: O(h). 
 Qual é o valor da altura h de uma árvore binária com N 
nós? 
 h = maior nível. 
 Melhor situação → árvore binária cheia (balanceada): 
 
 
 
 
 
 
 
 Nível k → 2k nós. 
 Propriedade: o número de nós de um nível k qualquer é 
igual a 1 mais a soma de todos os nós dos níveis 
anteriores. 
Altura de uma árvore binária 
14 
20 = 1 
21 = 2 
22 = 4 
23 = 8 
 Propriedade: o número de nós de um nível k qualquer é 
igual a 1 mais a soma de todos os nós dos níveis 
anteriores. 
 Aplicando a propriedade: 
Altura de uma árvore binária 
15 
nível 
0 
1 
2 
3 
... 
k 
... 
... 
h + 1 
número de nós 
20 = 1 
21 = 2 (1 + 1) 
22 = 4 (1 + 3) 
23 = 8 (1 + 7) 
... 
2k = 1+ 
... 
... 
2h +1 = 1 + 



1
0
2
k
i
i


h
i
i
0
2
 
 
 Mas, é o número total de nós da árvore (N), 
logo: 
 
 Aplicando-se log2, tem-se: 
 
 
 
 
 Eliminando as constantes, conclui-se que, numa 
árvore binária de busca balanceada, h é 
proporcional a log2 N. 
Altura de uma árvore binária 
16 
2h +1 = 1 + N 
log2 (2
h +1) = log2 (1 + N) 
h +1 = log2 (1 + N) 
h = log2 (1 + N) - 1 
2h +1 = 1 + 


h
i
i
0
2


h
i
i
0
2
 Pior situação → árvore binária desbalanceada 
(degenerada): 
Altura de uma árvore binária 
17 
Neste caso, h é proporcional a N. 
 Finalmente, pode-se afirmar: 
Altura de uma árvore binária 
18 
Complexidade : 
 o número de comparações é proporcional à altura h 
da árvore: O(h). 
 A altura da árvore binária é no mínimo log2N e no 
máximo N. 
 Portanto, a complexidade das operações em uma 
árvore binária de busca é O(log2N) na melhor 
situação (balanceada) e O(N) na pior situação 
(degenerada), onde N é o número de nós da árvore. 
 Para inserir um novo nó com o valor y, deve-se 
percorrer a árvore buscando a chave y, até 
encontrar o nó que será o seu pai, isto é, o nó 
que não apresentar filho na sequência natural do 
percurso (ou filho = NULL). 
 Em seguida, basta incluir um nó folha contendo 
y. 
19 
Inserção de um novo nó 
 Exemplo: inserir 14 e 27 na árvore abaixo. 
20 
20 
10 
30 
25 33 
8 15 
6 9 18 
Inserção de um novo nó 
 Inserir 14: 
 Busca chave 14 até encontrar o nó pai 
 Pai será o nó contendo 15. 
21 
20 
10 
30 
25 33 
8 15 
6 9 18 
Inserção de um novo nó 
 Inserir 14: 
 Inclui nó folha contendo 14 
22 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
Inserção de um novo nó 
 Inserir 27: 
 Busca chave 27 até encontrar o nó pai 
 Pai será o nó contendo 25. 
23 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
Inserção de um novo nó 
 Inserir 27: 
 Inclui nó folha contendo 27 
24 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
27 
Inserção de um novo nó 
A seguir são apresentadas as situações possíveis de 
inserção de um novo nó com o valor y, considerando 
que o nó contendo x foi identificado como pai. 
25 
r 
x 
nil nil 
raiz 
Nó folha 
r 
x 
nil y 
r 
x 
nil 
raiz 
Inserção de um novo nó 
y < x 
26 
r 
x 
nil nil 
raiz 
Nó folha 
r 
x 
nil 
raiz 
r 
x 
nil y 
Inserção de um novo nó 
y > x 
 Inserir chaves 15, 4, 20, 17, 19 
Exemplo de inserção 
27 
 Inserir chaves 15, 4, 20, 17, 19 
Exemplo de inserção 
28 
15 15 
4 
15 
4 20 
15 
4 20 
17 
15 
4 20 
17 
19 
Árvores Binárias 
29 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 bool AuxBusca(No*p, char C); 
 No* AuxInsere(No *p, char C); // insere novo nó 
 ... 
 No* Libera(No *p); 
 public: 
 TArvBinBusca(); 
 char ConsultaRaiz(); 
 void Insere(char C); // chama operador AuxInsere 
 bool Vazia(); 
 bool Busca(char C); 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
 Operação pública Insere: 
Inserção - Nó 
30 
void TArvBinBusca::Insere(char C) 
{ 
 // insere novo nó 
 No *p = AuxInsere(raiz, C); 
 if(raiz == NULL) 
 raiz = p; 
} 
void TArvBinBusca::Insere(char C) 
{ 
 // insere novo nó 
 raiz = AuxInsere(raiz, C); 
} 
ou 
 Operação privada AuxInsere: 
Inserção - Nó 
31 
No* TArvBinBusca::AuxInsere(No *p, char C) 
{ 
 if(p == NULL) 
 { 
 p = new No(); 
 p->atribInfo(C); 
 p->atribEsq(NULL); 
 p->atribDir(NULL); 
 } 
 else if(C < p->consultaInfo()) 
 p->atribEsq(AuxInsere(p->consultaEsq(), C)); 
 else 
 p->atribDir(AuxInsere(p->consultaDir(), C)); 
 return p; 
} 
 Construir a árvore binária de busca 
correspondente à inserção das seguintes chaves: 
 40, 30, 15, 50, 45, 13, 80, 71, 20 
Exercício - Inserção 
32 
 Na remoção de um nó da árvore binária de busca, o 
nível de complexidade depende da posição do nó a 
ser removido da árvore, pois ela deve preservar sua 
propriedade fundamental após a remoção. 
 Há três casos de remoção possíveis: quando o nó a ser 
removido 
1) é uma folha (não tem filhos)  caso mais simples 
2) tem somente 1 filho 
3) tem 2 filhos  caso mais difícil 
Remoção 
33 
15 
15 
4 
15 
4 20 
Caso 1 Caso 2 Caso 3 15 
20 
 Caso mais fácil de tratar. 
 O ponteiro apropriado de seu nó pai é ajustado 
para NULL e o nó é removido (liberando espaço 
da memória). 
 Exemplo: remover nó com conteúdo 19: 
1) Remover nó folha 
34 
15 
4 20 
17 19 1 
15 
4 20 
17 
19  Libera espaço 
1 
 Função privada para remover nó sem filho 
1) Remover nó folha 
35 
No* TArvBinBusca::RemoveFolha(No *p) 
{ 
 delete p; 
 return NULL; 
} 
Obs.: essa função só pode ser chamada a partir da 
certeza de que p aponta para um nó folha. 
Árvores Binárias 
36 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 No* RemoveFolha(No *p); // remove nó folha 
 No* AuxRemove(No *p, char C); // remove nó 
 ... 
 public: 
 TArvBinBusca(); 
 ... 
 void Remove(char C); // chama operador AuxRemove 
 ... 
 ~TArvBinBusca(); 
}; 
TAD ArvBinBusca 
 Ponteiro do pai do nó a ser removido é reajustado para 
apontar para o filho do nó a ser removido. 
 Ou seja, o pai vai apontar para o neto (que passa a ser filho). 
 Desse modo: 
 Descendentes do nó em questão são elevados em 1 nível 
2) Remover nó com 1 filho 
37 
 Exemplo: Remover nó 4 
2) Remover nó com 1 filho 
38 
 Libera espaço 15 
4 20 
17 19 1 
15 
20 
17 19 
1 
4 
 Função privada para remover nó com um filho: 
2) Remover nó com 1 filho 
39 
No* TArvBinBusca::Remove1Filho(No *p) 
{ 
 No *aux; 
 if(p->consultaEsq() == NULL) 
 aux = p->consultaDir(); 
 else 
 aux = p->consultaEsq(); 
 delete p; 
 return aux; 
} 
Obs.: essa função só pode ser chamada a partir da 
certeza de que p aponta para um nó que só tem 
um filho. 
Árvores Binárias 
40 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 No* RemoveFolha(No *p); 
 No* Remove1Filho(No *p); // remove nó com um filho 
 No* AuxRemove(No *p, char C); // remove nó 
 ... 
 public: 
 TArvBinBusca(); 
 ... 
 void Remove(char C); // chama operador AuxRemove 
 ... 
 ~TArvBinBusca(); 
}; 
TAD ArvBinBusca 
3) Remover nó com 2 filhos 
41 
50 
25 
15 
5 20 
35 
30 40 
Deseja-se 
excluir o nó 
25 
50 
15 
5 20 
35 
30 
40 
Substituir pela 
raiz da subárvore 
resolve o 
problema? 
 Se o nó a ser removido tem dois filhos: 
 Remover fazendo junção (merge). Não será visto. 
 Remover fazendo cópia 
3) Remover nó com 2 filhos 
42 
Remoção por cópia (Thomas Hibbard e Donald Knuth) 
Substituir o nó a ser removido pelo menor nó de sua sub-
árvore à direita e ajustar ponteiros. Para isso, o algoritmo 
deve executar as seguintes tarefas: 
 
 
 
 
 Buscar substituto (menor nó de sua sub-árvore à 
direita) 
 Trocar a informação do nó a ser excluído com a 
informação de seu substituto 
 Remover substituto (essa remoção faz o ajuste dos 
ponteiros) 
3) Remover nó com 2 filhos 
43 
Remoção por cópia (Thomas Hibbard e Donald Knuth) 
Substituir o nó a ser removido pelo menor nó de sua sub-
árvore à direita e ajustar ponteiros. Para isso, o algoritmo 
deve executar as seguintes tarefas: 
 Buscar o substituto (menor nó de sua sub-
árvore à direita) 
 Ir para a direita 
 Caminhar sempre para a esquerda até encontrar o 
nó que não tenha filho à esquerda (menor nó à 
esquerda). Este é o substituto. 
3) Remover nó com 2 filhos 
44 
3) Remover nó com 2 filhos 
45 
50 
25 
15 
5 20 
35 
30 40 
Seja excluir 
o nó 25 Ir para a 
direita 
Caminhar 
sempre 
para a 
esquerda 
Substituto!!! 
Exemplo 1: Exemplo 2: 
Ir para a 
direita 
Ele não 
possui filho 
à esquerda! 
Substituto!!! 
50 
25 
15 
5 20 
35 
40 
Seja excluir 
o nó 25 
3) Remover nó com 2 filhos 
46 
No* TArvBinBusca::Menor_SubArv_Direita(No *p) 
{ 
 No *aux = p->consultaDir(); 
 while(aux->consultaEsq() != NULL) 
 aux = aux->consultaEsq(); 
 return aux; 
} 
Acha o elemento mais à 
esquerda (menor) da 
subárvore à direita de p 
aux tem apenas um filho à 
direita ou não tem filho algum 
 Função privada para encontrar o menor 
elemento na subárvore da direita (nó mais à 
esquerda da subárvore da direita = substituto): 
Essa função só pode ser chamada a 
partir da certeza de que p aponta para 
um nó com dois filhos. 
Árvores Binárias 
47 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 void RemoveFolha(No *p); 
 void Remove1Filho(No *p); 
 No* Menor_SubArv_Direita(No *p); //retorna substituto 
 No* AuxRemove(No *p, char C); // remove nó 
 ... 
 public: 
 TArvBinBusca(); 
 ... 
 void Remove(char C); // chama operador AuxRemove 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
 Exemplo 1 
 Trocar a informação do nó com a de seu substituto 
 Remover substituto (ajustando os ponteiros) 
3) Remover nó com 2 filhos 
48 
50 
25 
15 
5 20 
35 
30 40 
Nó a ser 
excluido 
Troca 
valores 
Substituto!!! 
50 
30 
15 
5 20 
35 
25 40 
Substituto!!! Remover uma folha 
 Exemplo 1 
 Trocar a informação do nó com a de seu substituto 
 Remover substituto (ajustando os ponteiros) 
3) Remover nó com 2 filhos 
49 
50 
25 
15 
5 20 
35 
30 40 
Nó a ser 
excluido 
50 
30 
15 
5 20 
35 
40 
Situação final Situação inicial 
 Exemplo 2 
 Trocar a informação do nó com a de seu substituto 
 Remover substituto (ajustando os ponteiros) 
3) Remover nó com 2 filhos 
50 
50 
30 
15 
5 20 
35 
40 
Nó a ser 
excluido 
50 
35 
15 
5 20 
30 
40 
Troca 
valores 
Substituto!!! Substituto!!! 
Exclui 
substituto 
Remover nó com um só filho 
 Exemplo 2 
 Trocar a informação do nó com a de seusubstituto 
 Remover substituto (ajustando os ponteiros) 
3) Remover nó com 2 filhos 
51 
50 
30 
15 
5 20 
35 
40 
Nó a ser 
excluido 
50 
35 
15 
5 20 
40 
Situação final Situação inicial 
Árvores Binárias 
52 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 void RemoveFolha(No *p); 
 void Remove1Filho(No *p); 
 No* Menor_SubArv_Direita(No *p); 
 No* AuxRemove(No *p, char C); // remove nó 
 ... 
 public: 
 TArvBinBusca(); 
 ... 
 void Remove(char C); // chama operador AuxRemove 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
 Operação pública Remove do MI do TAD 
Inserção - Nó 
53 
void TArvBinBusca::Remove(char C) 
{ 
 // remove nó contendo C 
 raiz = AuxRemove(raiz, C); 
} 
Árvores Binárias 
54 
class TArvBinBusca 
{ 
 private: 
 No *raiz; 
 ... 
 No* RemoveFolha(No *p); 
 No* Remove1Filho(No *p); 
 No* Menor_SubArv_Direita(No *p); 
 No* AuxRemove(No *p, char C); // remove nó 
 ... 
 public: 
 TArvBinBusca(); 
 ... 
 void Remove(char C); // chama operador AuxRemove 
 ... 
 ~TArvBinBusca(); 
}; 
TAD TArvBinBusca 
 Operação AuxRemove do MI do TAD 
3) Remover nó com 2 filhos 
55 
No* TArvBinBusca::AuxRemove(No *p, char C) 
{ 
 if(p == NULL) 
 return NULL; 
 else if(C < p->consultaInfo()) 
 //remove na subarv. esquerda 
 p->atribEsq(AuxRemove(p->consultaEsq(), C)); 
 else if(C > p->consultaInfo()) 
 // remove na subarv. direita 
 p->atribDir(AuxRemove(p->consultaDir(), C)); 
 else 
 // continua ... 
 Operação AuxRemove do MI do TAD 
3) Remover nó com 2 filhos 
56 
 ... 
 else 
 {// achou o nó a ser removido, p->consultaInfo() == C 
 if((p->consultaEsq() == NULL) && 
 (p->consultaDir() == NULL)) 
 // p aponta para uma folha 
 p = RemoveFolha(p); 
 else if((p->consultaEsq() == NULL) || 
 (p->consultaDir() == NULL)) 
 //p tem só um filho 
 p = Remove1Filho(p); 
 else 
 // continua ... 
 Operação Remove do MI do TAD 
3) Remover nó com 2 filhos 
57 
 ... 
 else 
 {// p tem dois filhos 
 No *aux = Menor_SubArv_Direita(p); 
 // troca as informações 
 char auxch = aux->consultaInfo(); 
 p->atribInfo(auxch); 
 aux->atribInfo(C); 
 // recursão: para a subarv. direita 
 p->atribDir(AuxRemove(p->consultaDir(), C)); 
 } 
 } 
 return p; 
} 
 Remover 10 
Exemplo - Remoção 
58 
14 
20 
10 
30 
25 33 
8 17 
6 9 14 18 
20 
14 
30 
25 33 
8 17 
6 9 18 
Nó 14 é o menor nó 
à direita do nó 10 e 
não tem filho à 
direita. 
 Remover 10 
Exemplo - Remoção 
59 
14 
20 
10 
30 
25 33 
8 17 
6 9 14 18 
20 
14 
30 
25 33 
8 17 
6 9 18 
Nó 14 é o menor nó 
à direita do nó 10 e 
tem filho à direita. 
16 
16 
 Considere a seguinte árvore binária de busca 
Exemplo - Remoção 
60 
20 
10 
30 
25 33 
8 15 
6 9 14 18 
 Remover 14 
Exemplo - Remoção 
61 
20 
14 
30 
25 33 
8 15 
6 9 18 
20 
15 
30 
25 33 
8 18 
6 9 
 Remover 15 
Exemplo - Remoção 
62 
20 
18 
30 
25 33 
8 
6 9 
20 
15 
30 
25 33 
8 18 
6 9 
 Remover 18 
Exemplo - Remoção 
63 
20 
30 
25 33 
8 
6 9 
20 
18 
30 
25 33 
8 
6 9 
 Remover 6 
Exemplo - Remoção 
64 
20 
30 
25 33 
8 
9 
20 
30 
25 33 
8 
6 9 
 A partir da árvore binária de busca construída 
no exercício de inserção, contendo as chaves 40, 
30, 15, 50, 45, 13, 80, 71 e 20, executar as 
operações abaixo, apresentando a árvore 
resultante após a execução de cada operação. 
 Remover 50 
 Remover 30 
 Remover 13 
 Inserir 50 
 Remover 71 
Exercício 5 - Remoção 
65 
1. Fazer uma função para encontrar, e retornar, o maior 
elemento de uma árvore binária de busca. 
2. Fazer uma função para encontrar, e retornar, o menor 
elemento de uma árvore binária de busca. 
3. Fazer um procedimento para remover o maior elemento 
de uma árvore binária de busca. 
4. Fazer um procedimento para remover o menor elemento 
de uma árvore binária de busca. 
5. Alterar o(s) procedimento(s) de remoção de nó com dois 
filhos considerando, agora, o maior elemento da sub-
árvore à esquerda como o elemento a ser “trocado” com 
o nó a ser removido. 
Exercícios 
66 
6. Uma árvore binária de busca é considerada 
balanceada se sua altura h é próxima de 
log2(n). Fazer uma função para verificar se 
uma dada árvore binária de busca está 
balanceada. Considere uma árvore balanceada 
se h < log2(n) + 1. 
Exercícios 
67