04-ArvoresBinariasBusca

Prévia do material em texto

ÁRVORES BINÁRIAS DE BUSCA Vanessa BraganholoEstruturas de Dados e Seus 
Algoritmos 
REFERÊNCIA
Szwarcfiter, J.; Markezon, L. Estruturas de Dados e seus Algoritmos, 3a. ed. 
LTC. Cap. 4
INSTITUTO DE COMPUTAÇÃO - UFF 2
BUSCA
Diversas aplicações precisam buscar um determinado valor em um conjunto de dados
Essa busca deve ser feita da forma mais eficiente possível 
Árvores binárias possibilitam buscas com eficiência
Exemplo: buscar dados de uma pessoa que possui um determinado CPF
Dados das pessoas são armazenados numa árvore binária de busca 
CPF funciona como “chave”, pois é único para cada pessoa (não existem duas 
pessoas com o mesmo CPF)
INSTITUTO DE COMPUTAÇÃO - UFF 3
ÁRVORES BINÁRIAS DE BUSCA 
Apresentam uma relação de ordem entre os nós
Ordem é definida pela chave
esq chave info dir
Demais infos do nó
INSTITUTO DE COMPUTAÇÃO - UFF 4
ÁRVORES BINÁRIAS DE BUSCA
Uma árvore binária T é uma árvore 
binária de busca se: 
­ Chaves da subárvore esquerda de T são 
menores do que chave da raiz de T; e
­ Chaves da subárvore da direita de T são 
maiores do que a chave da raiz de T; e
­ Subárvores da esquerda e da direita de T são 
árvores binárias de busca
raiz500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 5
ÁRVORES BINÁRIAS DE BUSCA
Para um mesmo conjunto de chaves, 
existem várias árvores binárias de busca 
possíveis 
Exemplos para o conjunto de chaves: 
{1, 2, 3, 4, 5, 6, 7} 
INSTITUTO DE COMPUTAÇÃO - UFF 6
3
1 7
2 5
4 6
2
1 7
3
4
5
6
OPERAÇÕES
Buscar nó com determinada chave
Inserir novo nó
Remover nó
raiz500
300 800
150 400 900600
Operações devem preservar a 
ordem entre os nós! 
INSTITUTO DE COMPUTAÇÃO - UFF 7
BUSCA POR NÓ COM CHAVE X
raiz500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 8
Em qualquer nó: 
X = Chave
X > Chave
X < Chave
EXEMPLO: BUSCAR POR 600
raiz500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 9
EXEMPLO: BUSCAR POR 600
600 > 500 
Ir para direita 
INSTITUTO DE COMPUTAÇÃO - UFF 10
raiz500
300 800
150 400 900600
EXEMPLO: BUSCAR POR 600
600 < 800
Ir para a esquerda 
INSTITUTO DE COMPUTAÇÃO - UFF 11
raiz500
300 800
150 400 900600
EXEMPLO: BUSCAR POR 600
600 = 600
Achou
INSTITUTO DE COMPUTAÇÃO - UFF 12
raiz500
300 800
150 400 900600
EXEMPLO: BUSCAR POR 200
200 < 500
Ir para esquerda
200 < 300
Ir para esquerda
200 > 150 
Ir para a direita
NULL: chave não encontrada
INSTITUTO DE COMPUTAÇÃO - UFF 13
raiz500
300 800
150 400 900600
BUSCA POR NÓ COM DETERMINADA CHAVE
esq chave info dir/* representação dos nós de a */ 
typedef struct sNoA {
char info;
int chave;
struct sNoA* esq;
struct sNoA* dir;
} TNoA;
TNoA* busca(TNoA *no, int chave) {
//Recebe endereço da raiz e chave procurada. 
Se encontrar, retorna ponteiro p/ nó 
encontrado. 
//Caso contrário, retorna NULO
}
Fazer agora!
INSTITUTO DE COMPUTAÇÃO - UFF 14
IMPLEMENTAÇÃO ITERATIVA
TNoA* busca(TNoA *no, int chave) {
TNoA *aux = no;
while (aux != NULL) {
if (aux->chave == chave )
return aux; //achou retorna o ponteiro para o nó
else
if (aux->chave > chave)
aux = aux->esq;
else
aux = aux->dir;
}
return NULL; //não achou, retorna null
}
INSTITUTO DE COMPUTAÇÃO - UFF 15
IMPLEMENTAÇÃO RECURSIVA
TNoA* buscaRecursiva(TNoA *no, int chave) {
if (no == NULL)
return NULL;
else if (no->chave == chave)
return no;
else if (no->chave > chave)
return buscaRecursiva(no->esq, chave);
else
return buscaRecursiva(no->dir, chave);
}
INSTITUTO DE COMPUTAÇÃO - UFF 16
COMPLEXIDADE
Em cada chamada da função busca, é efetuado um número constante de operações.
A complexidade da busca é igual ao número de chamadas da função. 
No pior caso (quando chave buscada está na folha), a complexidade é a altura da 
árvore.
Complexidade mínima de pior caso ocorre para árvore completa, onde altura é log 
n (n é o número de nós da árvore). 
Portanto, o ideal é que a árvore binária de busca seja o mais balanceada possível.
INSTITUTO DE COMPUTAÇÃO - UFF 17
INSERÇÃO
Se a árvore for vazia, instala o novo nó na raiz
Se não for vazia, compara a chave com a chave da raiz:
­ se for menor, instala o nó na sub-árvore da esquerda
­ caso contrário, instala o nó na sub-árvore da direita
IMPORTANTE: nó é sempre inserido como uma folha
INSTITUTO DE COMPUTAÇÃO - UFF 18
INSERÇÃO
Se a árvore for vazia, instala o novo nó na raiz
Se não for vazia, compara a chave com a chave da raiz:
­ se for menor, instala o nó na sub-árvore da esquerda
­ caso contrário, instala o nó na sub-árvore da direita
INSTITUTO DE COMPUTAÇÃO - UFF 19
Ordem de Inserção: 
500 – 800 – 300 - 400
500
INSERÇÃO
Se a árvore for vazia, instala o novo nó na raiz
Se não for vazia, compara a chave com a chave da raiz:
­ se for menor, instala o nó na sub-árvore da esquerda
­ caso contrário, instala o nó na sub-árvore da direita
INSTITUTO DE COMPUTAÇÃO - UFF 20
Ordem de Inserção: 
500 – 800 – 300 - 400
500
800
INSERÇÃO
Se a árvore for vazia, instala o novo nó na raiz
Se não for vazia, compara a chave com a chave da raiz:
­ se for menor, instala o nó na sub-árvore da esquerda
­ caso contrário, instala o nó na sub-árvore da direita
INSTITUTO DE COMPUTAÇÃO - UFF 21
Ordem de Inserção: 
500 – 800 – 300 - 400
500
300 800
INSERÇÃO
Se a árvore for vazia, instala o novo nó na raiz
Se não for vazia, compara a chave com a chave da raiz:
­ se for menor, instala o nó na sub-árvore da esquerda
­ caso contrário, instala o nó na sub-árvore da direita
500
300 800
INSTITUTO DE COMPUTAÇÃO - UFF 22
Ordem de Inserção: 
500 – 800 – 300 - 400
400
+ 380
500
300 800
150 400 900600
raizEXEMPLO
INSTITUTO DE COMPUTAÇÃO - UFF 23
+ 380
500
300 800
150 400 900600
raiz
380
EXEMPLO
INSTITUTO DE COMPUTAÇÃO - UFF 24
+ 380
+ 750
500
300 800
150 400 900600
raiz
380
EXEMPLO
INSTITUTO DE COMPUTAÇÃO - UFF 25
+ 380
+ 750
500
300 800
150 400 900600
raiz
380 750
EXEMPLO
INSTITUTO DE COMPUTAÇÃO - UFF 26
EXERCÍCIOS
1. Inserir em uma ABB inicialmente vazia, os seguintes valores:
25, 22, 40, 30, 45, 27, 20, 21, 48 
2. Inserir em uma ABB inicialmente vazia, os seguintes valores: 
40, 25, 20, 30, 45, 27, 22, 21, 48
INSTITUTO DE COMPUTAÇÃO - UFF 27
INSERÇÃO
25 22 40 30 45 27 20 21 48
22
25
40
20 30 45
21 27 48
40 25 20 30 45 27 22 21 48
25
40
45
20 30
21
22
48
27
INSTITUTO DE COMPUTAÇÃO - UFF 28
INSERÇÃO
25 22 40 30 45 27 20 21 48
A árvore gerada depende da ordem 
de inserção dos nós
22
25
40
20 30 45
21 27 48
40 25 20 30 45 27 22 21 48
25
40
45
20 30
21
22
48
27
INSTITUTO DE COMPUTAÇÃO - UFF 29
IMPLEMENTAÇÃO DE INSERÇÃO
TNoA *insere(TNoA *no, int chave) {
if (no == NULL) {
no = (TNoA *) malloc(sizeof(TNoA));
no->chave = chave;
no->esq = NULL;
no->dir = NULL;
} else if (chave < (no->chave))
no->esq = insere(no->esq, chave);
else if (chave > (no->chave)) 
no->dir = insere(no->dir, chave);
else {
printf("Inserção inválida! "); // chave já existe
exit(1);
}
return no;
}
INSTITUTO DE COMPUTAÇÃO - UFF 30
IMPLEMENTAÇÃO DE INSERÇÃO
TNoA *insere(TNoA *no, int chave) {
if (no == NULL) {
no = (TNoA *) malloc(sizeof(TNoA));
no->chave = chave;
no->esq = NULL;
no->dir = NULL;
} else if (chave < (no->chave))
no->esq = insere(no->esq, chave);
else if (chave > (no->chave)) 
no->dir = insere(no->dir, chave);
else {
printf("Inserção inválida! "); // chave já existe
exit(1);
}
return no;
}
INSTITUTO DE COMPUTAÇÃO - UFF 31
Árvore Binária de Busca não 
pode ter chave duplicada
PROBLEMA
A ordem em que as chaves são inseridas numa árvore de busca binária pode fazer 
com que uma árvore se deteriore, ficando com altura muito grande. 
Exemplo: 
INSTITUTO DE COMPUTAÇÃO - UFF 32
25 40 39 27 
25
40
39
27
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Sabendo disso, é possível reordenar as chaves de entrada de forma a obter uma 
árvore o mais balanceada possível. 
Algoritmo: 
­ Seja v um vetor ORDENADO contendoas chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços que sobraram
INSTITUTO DE COMPUTAÇÃO - UFF 33
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 34
150 300 400 500 600 800 900
500
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 35
150 300 400 500 600 800 900
500
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 36
150 300 400 500 600 800 900
500
300
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 37
150 300 400 500 600 800 900
500
300
150
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 38
150 300 400 500 600 800 900
500
300
150 400
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 39
150 300 400 500 600 800 900
500
300
150 400
800
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 40
150 300 400 500 600 800 900
500
300
150 400
800
600
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 41
150 300 400 500 600 800 900
500
300
150 400
800
600 900
CRIAÇÃO DE ÁRVORE BINÁRIA DE BUSCA MAIS 
BALANCEADA POSSÍVEL
Algoritmo: 
­ Seja v um vetor ORDENADO contendo as 
chaves a serem inseridas 
­ Inserir a chave do meio
­ Chamar recursivamente para os dois pedaços 
que sobraram (esquerda e direita)
INSTITUTO DE COMPUTAÇÃO - UFF 42
500
300 800
150 400 900600
150 300 400 500 600 800 900
IMPLEMENTAÇÃO
INSTITUTO DE COMPUTAÇÃO - UFF 43
void criaArvoreBalanceada(TNoA *raiz, int v[], int inicio, int fim) {
if (inicio <= fim) {
int meio = (inicio + fim) / 2;
raiz = insere(raiz, v[meio]);
//constroi subárvores esquerda e direita
criaArvoreBalanceada(raiz, v, inicio, meio - 1);
criaArvoreBalanceada(raiz, v, meio + 1, fim);
}
}
int main(void) {
int tam = 7;
int v[] = {150, 300, 400, 500, 600, 800, 900};
TNoA *raiz;
raiz = NULL;
criaArvoreBalanceada(raiz,v,0,tam-1);
imprime(raiz, 0);
};
EXCLUSÃO
?
500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 44
Fonte de Referência:
Celes, W., Cerqueira, R., Rangel, J.L. 
Introdução a Estruturas de Dados, 
Campus, 1a Edição, 2004. 
EXCLUSÃO
Exclusão Física
3 casos
­ Nó é folha
­ Nó não folha
­ Possui uma subárvore
­ Possui duas subárvores
500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 45
EXCLUSÃO – CASO 1: NÓ FOLHA
500
300 800
150 400 900600
INSTITUTO DE COMPUTAÇÃO - UFF 46
Quando o nó a ser excluído é uma folha, basta removê-lo
(lembrar de desalocar memória)
EXCLUSÃO – CASO 1: NÓ FOLHA
500
300 800
150 900600
INSTITUTO DE COMPUTAÇÃO - UFF 47
Quando o nó a ser excluído é uma folha, basta removê-lo
(lembrar de desalocar memória)
EXCLUSÃO – CASO 2: NÓ INTERNO COM APENAS 
UMA SUBÁRVORE
Raiz da subárvore passa a ocupar o lugar do nó excluído
550 650
500
300 800
150 400 600
INSTITUTO DE COMPUTAÇÃO - UFF 48
EXCLUSÃO – CASO 2: NÓ INTERNO COM APENAS 
UMA SUBÁRVORE
Raiz da subárvore passa a ocupar o lugar do nodo excluído
550 650
500
300
150 400
600
INSTITUTO DE COMPUTAÇÃO - UFF 49
EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES
Reestruturar a árvore
550 650
500
300 800
150 400 600 900
INSTITUTO DE COMPUTAÇÃO - UFF 50
EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES
Estratégia Recursiva
­ Trocar o valor do nó a ser removido com
­ valor do nó que tenha a maior chave da sua subárvore à esquerda (será o que adotaremos em aula); OU
­ valor do nó que tenha menor chave da sua subárvore à direita
­ Ir à subárvore onde foi feita a troca e remover o nó
INSTITUTO DE COMPUTAÇÃO - UFF 51
EXCLUSÃO – CASO 3: NÓ POSSUI 2 SUBÁRVORES
550 650
500
300 800
150 400 600 900
550
500
300 650
150 400 600 900
Þ
INSTITUTO DE COMPUTAÇÃO - UFF 52
EXCLUSÃO DO NÓ DE CHAVE 80
200
100 300
150
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 53
1º. Caso: nó folha 80
EXCLUSÃO DO NÓ DE CHAVE 80
200
100 300
150
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 54
1º. Caso: nó folha
EXCLUSÃO DO NÓ DE CHAVE 150
200
100 300
15080
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 55
2º. Caso: nó com 
apenas 1 subárvore
EXCLUSÃO DO NÓ DE CHAVE 150
200
100 300
80 120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 56
2º. Caso: nó com 
apenas 1 subárvore
EXCLUSÃO DO NÓ DE CHAVE 300
200
100 300
15080 250
220 270
260
400
350 500
280
275 290
INSTITUTO DE COMPUTAÇÃO - UFF 57
3º. Caso: nó com 2 subárvores
EXCLUSÃO DO NÓ DE CHAVE 300
200
100 300
15080 250
220 270
260
400
350 500
280
275 290
INSTITUTO DE COMPUTAÇÃO - UFF 58
Encontrar maior valor da 
subárvore esquerda
EXCLUSÃO DO NÓ DE CHAVE 300
200
100 290
15080 250
220 270
260
400
350 500
280
275 290
INSTITUTO DE COMPUTAÇÃO - UFF 59
Encontrar maior valor da 
subárvore esquerda e substituir 
o nó a ser excluído por uma 
cópia do nó encontrado
EXCLUSÃO DO NÓ DE CHAVE 300
200
100 290
15080 250
220 270
260
400
350 500
280
275 290
INSTITUTO DE COMPUTAÇÃO - UFF 60
Excluir 290 (1º. Caso)
EXCLUSÃO DO NÓ DE CHAVE 300
200
100 290
15080 250
220 270
260
400
350 500
280
275
INSTITUTO DE COMPUTAÇÃO - UFF 61
FIM
EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA 
ÁRVORE)
200
100 300
15080
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 62
3º. Caso: nó com 2 
subárvores
EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA 
ÁRVORE)
200
100 270
15080
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 63
Encontrar maior valor da 
subárvore esquerda e substituir 
o nó a ser excluído por uma 
cópia do nó encontrado
EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA 
ÁRVORE)
200
100 270
15080
120
110 130
250
220 270
260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 64
Excluir 270 (2º. Caso)
EXCLUSÃO DO NÓ DE CHAVE 300 (OUTRA 
ÁRVORE)
200
100 270
15080
120
110 130
250
220 260
400
350 500
INSTITUTO DE COMPUTAÇÃO - UFF 65
FIM
EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO 
EXEMPLO) 200
100 300
15080 250
220 270
260
400
350 500
255 265 INSTITUTO DE COMPUTAÇÃO - UFF 66
3º. Caso: nó com 2 subárvores
EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO 
EXEMPLO) 200
100 300
15080 250
220 270
260
400
350 500
255 265 INSTITUTO DE COMPUTAÇÃO - UFF 67
Encontrar maior valor da 
subárvoreesquerda e substituir 
o nó a ser excluído por uma 
cópia do nó encontrado
EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO 
EXEMPLO) 200
100 270
15080 250
220 270
260
400
350 500
255 265 INSTITUTO DE COMPUTAÇÃO - UFF 68
Encontrar maior valor da 
subárvore esquerda e substituir 
o nó a ser excluído por uma 
cópia do nó encontrado
EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO 
EXEMPLO) 200
100 270
15080 250
220 270
260
400
350 500
255 265 INSTITUTO DE COMPUTAÇÃO - UFF 69
Excluir 270 (2º. Caso)
EXCLUSÃO DE NÓ DE CHAVE 300 (TERCEIRO 
EXEMPLO) 200
100 270
15080 250
220 260
400
350 500
255 265
INSTITUTO DE COMPUTAÇÃO - UFF 70
FIM
EXERCÍCIO
Dada a árvore a seguir, executar o 
procedimento de exclusão cumulativo 
dos seguintes nós: 
100 – 150 – 80 – 270 – 400 – 200 
INSTITUTO DE COMPUTAÇÃO - UFF 71
200
100 300
15080
120
110 130
250
220 270
260
400
350 50070
65 79
CONSIDERAÇÕES FINAIS
Para grandes volumes de dados, árvores binárias de busca não são as alternativas 
mais eficientes. 
Ao longo da disciplina veremos outras alternativas para buscas eficientes em 
grandes volumes de dados (Tabelas Hash, Árvores B, Árvores B+).
INSTITUTO DE COMPUTAÇÃO - UFF 73
AGRADECIMENTOS
Material baseado nos slides de Renata Galante, UFRGS
INSTITUTO DE COMPUTAÇÃO - UFF 74