aula05

Prévia do material em texto

5ºAula
ÁRVORES DE BUSCA BINÁRIA – 
PARTE II
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• entender como funciona o processo de inserção em uma ABB;
• entender como funciona o processo de remoção em uma ABB.
Olá,
Nesta aula, vamos prosseguir com os estudos da Árvore 
de Busca Binária (ABB), uma das estruturas de dados mais 
elementares da área da Computação. Agora, vamos aprender 
como inserir e remover dados nessa árvore.
Leiam atentamente esta aula e façam os exercícios. Se 
enfrentarem alguma dúvida, estaremos a sua disposição na área 
do aluno.
Bons estudos!
33
Estrutura de Dados II 32
1. 
Seções de estudo
Inserção em uma Árvore de Busca Binária
2. Remoção em uma Árvore de Busca Binária
1 - Inserção em uma Árvore de Busca 
Binária
Na primeira aula, mostramos a vocês o que é uma Árvore 
de Busca Binária e algumas operações, como: percurso de 
dados, determinação do menor ou maior valor de uma árvore 
e busca de dados. Mas ainda, não vimos como criar uma árvore 
de busca binária.
Nós criamos uma árvore de busca binária com as 
operações de inserção de dados. Aprender essa operação não 
é algo complicado, quando você aprende os fundamentos de 
uma árvore de busca binária. Inserimos os elementos que são 
menores a esquerda e os elementos que são maiores a direita.
Primeiramente, devemos alocar o novo nó. Criamos 
esse novo nó colocando o dado a ser inserido e atribuindo os 
valores dos ponteiros esquerda e direita como NULO. 
Depois, definimos onde vamos inserir esse nó, definindo 
qual será o pai desse nó. O processo é similar a busca em 
uma árvore de busca binária, percorrendo elementos até 
encontrarmos uma posição para o nó. Para entender esse 
processo, observem essa árvore de busca binária:
Suponhamos que queremos inserir o valor 20 nessa árvore 
binária. Vamos aos passos para procurar o pai.
• Primeiro, vasculhamos a raiz da árvore. Como 20 é 
menor que 30, vamos para o próximo nó do lado 
esquerdo da árvore.
• Em seguida, comparamos o valor 13. Como 20 é 
maior que 13, vamos para o filho direito da árvore.
• Em seguida, comparamos o valor 17. Como 20 é 
maior que 17, vamos para o filho direito da árvore.
• Depois, verificamos o valor 21. Como o valor 20 é 
menor que 21, vamos para o filho esquerdo da árvore.
• Como não existe um filho esquerdo para o nó de 
valor 21 na árvore, paramos por aqui e consideramos 
o nó de valor 21 como sendo o pai.
Portanto, o processo de definição do pai consiste em uma 
busca, até atingir algum ponteiro de valor NULO. Quando 
chegar a esse ponteiro, o valor procurado anteriormente será 
o pai do novo nó.
Definido o pai, o processo de inserção se resumirá apenas 
em definir de qual lado do nó pai será posicionado o novo 
nó. Se o novo dado for menor que o pai, ele será posicionado 
a esquerda. Se o novo dado for maior que o pai, ele será 
posicionado a direita.
Vale lembrar que o processo de escolha do pai terá uma 
variável chamada pai, que inicialmente receberá um valor 
NULO. Em seguida, o processo de busca começa. Porém, 
se não tivermos elementos na árvore, o processo não será 
realizado, e o valor de pai ainda será NULO. Nesse caso, a raiz 
será o novo nó.
34
33
Agora, vamos mostrar o algoritmo de inserção de 
dados na árvore binária.
Agora que vocês sabem como inserir, vamos mostrar 
como remover os elementos em uma árvore de busca 
binária.
procedimento insere(chave: inteiro, Raiz: 
*TArvore)
declare
 NovoNo, Pai, Atual: *TArvore
inicio
 // Cria o novo nó
 NovoNo <- novo TArvore
 NovoNo->dado <- chave
 NovoNo->esq <- NULO
 NovoNo->dir <- NULO
 
 // Agora vamos procurar o pai
 Pai <- NULO;
 Atual <- Raiz
 enquanto (Atual NULO)
 Pai <- Atual;
 se (chave < Pai->dado) entao
 Atual <- Pai->esq
 senao
 Atual <- pai->dir
 fimse
 fimse
 
 // Com o pai encontrado, colocamos
 // o novo nó como sendo o seu filho
 
 se (Pai = NULO) entao
 Arvore.raiz <- NovoNo
 senao
 se (chave < Pai->dado) entao
 Pai->esq <- NovoNo
 senao
 Pai->dir <- NovoNo
 fimse
 fimse
 
fimprocedimento
2 - Remoção em uma Árvore de 
Busca Binária
Existem várias formas de se fazer uma remoção em 
uma Árvore de Busca Binária. Nesta aula, vamos abordar a 
remoção por cópia definido por Cormen et. al. (2012). 
Precisamos remover dados quando não precisamos, 
mas temos que manter as premissas de uma árvore de 
busca binária, para que os algoritmos de busca e inserção 
funcionem normalmente.
Para isso, precisamos saber se o dado a ser removido 
possui filhos ou não. Devido a natureza de uma árvore 
binária, isso gera três casos possíveis:
• O nó a ser removido não possui filhos: Apenas 
retiramos ele da árvore.
• O nó a ser removido possui um filho: Ligamos o 
seu filho ao seu avô (ou seja, o pai do elemento a 
ser removido). Caso não tenha um avô, significa 
que estamos deletando a raiz da árvore. Assim, 
promovemos o seu filho a condição de raiz.
• O nó a ser removido possui dois filhos: Definimos 
o maior elemento depois do dado a ser removido, 
denominado de sucessor. Esse sucessor fica na 
subárvore direita do nó a ser removido e pode 
ou não ser filho direto do nó a ser removido. 
Definido o seu sucessor, promovemos ele, ao 
lugar onde estava o nó removido, e ligamos o resto 
da subárvore direita e a subárvore esquerda do nó 
removido ao nó sucessor promovido.
Vamos agora explicar como funciona o processo de 
remoção. Ele consiste em três situações, que aplicam os 
casos mostrados anteriormente. Vejamos as situações a 
seguir:
1. Se NoRemover (nó a ser removido) não tiver 
um filho a esquerda (representado no quadro “a” 
da Figura 3, que será apresentado mais adiante), 
substituímos NoRemover pelo seu filho à direita, 
que pode ser nulo ou não. Se seu filho direito 
for nulo, temos o caso de quando o nó não tem 
filhos. Se o filho direito existir, é tratado o caso de 
quando temos um filho à direita.
2. Se NoRemover tiver apenas um filho, que é o seu 
filho à esquerda, substituímos esse nó removido 
pelo seu único filho (representado pelo quadro 
“b” da Figura 3).
3. Se o nó a ser removido tiver os dois filhos, 
temos que verificar qual é o sucessor do nó a ser 
removido. Isso é obtido através do cálculo do 
menor elemento da subárvore direita do nó a ser 
removido (vejam a aula 03 para saber mais). Com 
o sucessor em mãos, verificamos se ele é filho 
direto do nó a ser removido. Isso implica em duas 
situações extras:
a. Se o sucessor não for filho do nó a ser removido, 
substituímos o sucessor pelo seu próprio filho a direita e 
depois substituímos o nó a ser removido pelo sucessor 
(parte “d” da Figura 3).
b. Se o sucessor for filho direto do nó a ser removido, 
substituímos NoRemover pelo seu sucessor, deixando o 
filho à direita do sucessor sozinho (parte “c” da Figura 3).
35
Estrutura de Dados II 34
Para que esse algoritmo funcione, temos que usar 
algumas funções auxiliares. A primeira delas é a função pai, 
que define o pai de um nó. Ele tem o mesmo funcionamento 
da parte que se encarregou de definir o pai no algoritmo de 
inserção.
funcao pai(No: *Tarvore): *TArvore
declare
 Pai, Atual : *TArvore
inicio
 Pai <- NULO
 Atual <- No;
 enquanto (Atual NULO)
 Pai <- Atual
 se (chave < Pai->dado) entao
 Atual <- Pai->esq
 senao
 Atual <- pai->dir
 fimse
 fimse
 retorne Pai
fimfuncao
Uma outra função que vamos usar se chama transplantar, 
que consiste em substituir uma subárvore como um filho de 
seu pai por uma outra subárvore. São dados dois argumentos, 
que são ponteiros para nós raízes de duas subárvores: u e v. 
Três situações podem ocorrer:
1. Se o nó u não tiver um pai, o nó v será considerado 
a nova raiz da árvore.
2. Se o nó u for um filho do lado esquerdo da árvore, 
o ponteiro esquerdo do pai de u recebe o ponteiro v.
3. Se o nó u for um filho do lado direitoda árvore, o 
ponteiro direito do pai de u recebe o ponteiro v.
Com isso em mente, vamos ao código do procedimento:
procedimento transplantar(u: *TArvore, v: 
*TArvore)
36
35
declare
 pai_u *TArvore
inicio
 pai_u <- pai(u)
 se (pai_u = NULO) entao
 Arvore.raiz <- v // Caso 1
 senao
 se (u = pai_u->esq) entao
 pai_u->esq <- v // Caso 2
 senao
 pai_u->dir <- v // Caso 3
 fimse
 fimse
fimprocedimento
Feito isso, vamos mostrar todo o código do procedimento 
de remoção.
procedimento remove(NoRemover: *TArvore, 
Raiz: *TArvore)
declare
 Sucessor, PaiSucessor: *TArvore
inicio
 // Parte 1 - so o filho a direita
 se (NoRemover->esq NULO) entao
 transplantar(NoRemover, NoRemover-
>dir)
 senao
 
 // Parte 2 - só o filho a esquerda
 se (NoRemover->dir NULO) entao
 transplantar(NoRemover, NoRemover-
>esq)
 
 senao
 
 // Parte 3 - os dois filhos
 // Define o sucessor de NoRemover
 Sucessor <- minimo(NoRemover-
>dir);
 
 se (pai(Sucessor) NoRemover) 
entao
 // NoRemover não é o pai de 
Sucessor
 transplantar(Sucessor, 
Sucessor->dir)
 Sucessor->dir = NoRemover-
>dir
 fimse
 
 transplantar(NoRemover, Sucessor)
 Sucessor->esq <- NoRemover->esq
 fimse
 fimse
fimprocedimento
E com isso, finalizamos a nossa aula. Na próxima aula, 
vamos ver as árvores AVL. Até a próxima!
Retomando a aula
Encerramos a nossa quinta aula. Vamos relembrar o 
que vimos?
1 - Inserção em uma Árvore de Busca Binária
Nesta seção, vimos como funciona o processo de inserção 
de elementos em uma árvore de busca binária. Ela consiste 
em três passos: Inicializar o novo nó, definir qual será o pai 
desse nó (isso é feito através de uma pesquisa, procurando em 
qual extremidade será instalado o nó) e depois ligar o nó a esse 
pai, obedecendo a regra: Se for menor do que o pai, salva do 
lado esquerdo. Se for maior, salva do lado direito.
2 - Remoção em uma Árvore de Busca Binária
Nesta seção, vimos como remover um elemento em 
uma árvore binária. Para isso, devemos verificar se o nó a ser 
removido possui algum filho. Se tiver, promovemos o filho a 
posição do seu pai. Caso o nó a ser removido tenha os dois 
filhos, devemos procurar o sucessor do seu nó e promovê-lo 
a posição do nó removido.
CORMEN, Thomas H.; et. al.. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
KNUTH, Donald Ervin. The art of computer programming. 
3. ed. Amsterdam: Addison-Wesley, 1998.
SZWARCFITER, Jayme Luiz; MARKENZON, 
Lilian. Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: 
LTC, 1994.
TENENBAUM, Aaron M.; AUGENSTEIN, Moshe 
J.; LANGSAN, Yedidyah. et al. Estruturas de dados usando 
C. São Paulo: Pearson Makron Books; São Paulo: Makron 
Books do Brasil; São Paulo: McGraw-Hill, 2013.
ZIVIANI, Nivio. Projeto de algoritmos: com implementação 
em PASCAL e C. 3. ed. São Paulo: Cengage Learning, 2011.
Vale a pena ler
Vale a pena
37
Estrutura de Dados II 36
FEOFLIOFF, Paulo. Árvores binárias de busca. USP, 
2018. Disponível em: < https://www.ime.usp.br/~pf/
algoritmos/aulas/binst.html >. Acesso em: 15 set. 2018. 
GALLES, David. Binary Search Tree (Simulador de 
Árvore Binária). USF, s.d. Disponível em: < https://www.
cs.usfca.edu/~galles/visualization/BST.html >. Acesso em: 
15 set. 2018. 
Vale a pena acessar
Minhas anotações
38