AULA_8_RevisaoArvoreBinariaPesquisa

Prévia do material em texto

Algoritmo e Estrutura de Dados II 
COM 112 
Vanessa Souza 
Universidade Federal de Itajubá – Instituto de Matemática e Computação 
Aula 8 
Árvore de pesquisa binária 
 Estrutura de dados não linear 
 
 Além de um campo chave e dos dados satélite, cada 
nó contém os campos esquerda, direita e pai, que 
apontam para os nós correspondentes a seu filho da 
esquerda, seu filho da direita e seu pai, 
respectivamente. 
 Se o nó for folha, os filhos da esquerda e da direita recebem 
NULL 
Árvore de pesquisa binária 
 Estrutura de dados não linear 
 
 Operações 
 Cria árvore 
 Insere nó na árvore 
 Percorre os nós da árvore 
 Pré-ordem 
 Ordem 
 Pós-ordem 
 Remove nó da árvore 
 Maior 
 Menor 
Árvore de pesquisa binária 
 Operações 
 Cria árvore 
 Cria o sentinela e devolve seu endereço, que será único 
durante toda execução do programa. 
 
Árvore de pesquisa binária 
 Operações 
 Insere nó na árvore 
 Insere um nó na árvore binária. 
 Se a árvore estiver vazia, cria a raiz 
 Se a árvore tiver elementos, adiciona seguindo a regra de menores 
a esquerda, maiores a direita. 
 
5 é raiz da árvore 
Árvore de pesquisa binária 
 Operações 
 Insere nó na árvore 
 Insere um nó na árvore binária. 
 Se a árvore estiver vazia, cria a raiz 
 Se a árvore tiver elementos, adiciona seguindo a regra de menores 
a esquerda, maiores a direita. 
 
Inserir 7 e 3 na árvore 
Árvore de pesquisa binária 
 Operações 
 Percorre os nós da ávore 
 Pré-ordem: raiz, esq, dir – 5,3,7 
 Ordem : esq, raiz, dir – 3,5,7 
 Pós-ordem: esq, dir, raiz – 3,7,5 
 
Remoção 
 Uma operação mais complicada é a remoção de um 
nó de uma árvore binária de procura. 
 
 Para removermos um nó X de uma árvore de busca 
binária preservando suas propriedades, precisamos 
considerar três casos: 
 X não possui nenhum filho (folha). 
 X possui apenas um filho. 
 X possui dois filhos. 
 + complexidade 
Remoção 
 Caso 1 : Nó folha 
 Remoção simples. Basta fazer o pai do nó apontar para 
NULL 
Lembrar de liberar a memória do nó 3 
Remover o nó 3 
Remoção 
 Caso 2 : O nó tem apenas um filho 
 Basta modificar o ponteiro no nó pai de X para que ele 
aponte para o filho de X. 
Lembrar de liberar a memória do nó 8 
Remover o nó 8 
Remoção 
 Caso 3 : O nó tem dois filhos 
 O caso mais complicado ocorre quando o nó a ser 
removido tem dois filhos (ou seja, é pai de uma 
subárvore esquerda e de uma subárvore direita). 
 
 Um algoritmo possível é conhecido como remoção por 
cópia. 
 
Remoção 
 Caso 3 : O nó tem dois filhos 
 O algoritmo consiste em encontrar o sucessor (ou 
predecessor) imediato do nó a ser removido e substituir 
este nó por seu sucessor (ou predecessor). 
 O sucessor de um nó X é o nó com a menor chave 
maior que X 
 Filho mais à esquerda, da subárvore da direita de X 
 Se o sucessor for folha, basta copiar a chave e os dados 
satélites do sucessor para o lugar do nó X e remover o 
sucessor. 
 Se o sucessor tiver um filho, faz a remoção do sucessor e 
copia os dados do sucessor para o lugar do nó X. 
Remoção 
 Exemplo : Remover o nó 4 
 
 Passo 1 : tem dois filhos 
 Passo 2 : encontra sucessor – 5 
 Passo 3 : 5 é folha 
 Passo 4 : copia os dados do 
sucessor para o nó a ser 
removido. 
 Passo 5 : remove a folha 
Remoção 
 Exemplo : Remover o nó 7 
 
 Passo 1 : tem dois filhos 
 Passo 2 : encontra sucessor – 8 
 Passo 3 : 8 tem um filho 
 Passo 4 : copia os dados do 
sucessor para o nó a ser 
removido. 
 Passo 5 : remove o nó com 1 
filho 
Remoção 
 Exercício 
 Dada a árvore abaixo, remover sucessivamente os nós 13, 
16, 5 e 20, utilizando o sucessor. 
 
Remoção 
 Exercício 
 Dada a árvore abaixo, remover sucessivamente os nós 13, 
16, 5 e 20, utilizando o predecessor. 
Remoção 
 Vamos implementar?? 
Remoção 
Remoção 
 Para casa: 
 Implementar as funções: 
Considerações 
 Dependendo da ordem das Inserções e da 
quantidade de remoções sucessivas, a árvore pode 
tornar-se desbalanceada. 
 Problema : a árvore pode virar uma lista. 
 Perde-se a característica de árvore e as vantagens 
associadas a ela. 
 
Considerações 
 Dependendo da ordem das Inserções e da 
quantidade de remoções sucessivas, a árvore pode 
tornar-se desbalanceada. 
 Problema : a árvore pode virar uma lista. 
 Perde-se a característica de árvore e as vantagens 
associadas a ela. 
 SOLUÇÃO: 
 Balanceamento