AEDS3 Arvore Binaria Busca

Prévia do material em texto

1 
 
Definição do problema: 
 O TP1 tem a proposta de inserir o aluno à prática da programação da 
estrutura fundamentada em sala de aula. A proposta objetiva seria a 
implementação de uma árvore binária de busca (NÃO BALANCEADA) acompanhada 
das seguintes funções: 
 Adicionar uma chave 
 Pesquisar se uma chave está ou não inserida na arvore 
 Remoção de uma chave específica 
 Exibição de todas as chaves cadastradas na arvore em ordem 
crescente 
 Questionar o balanceamento da arvore cadastrada 
 Remover todos os nós folhas da arvore cadastrada 
Primeiro relembramos o conceito de arvores binárias de busca: 
“Arvore binária de busca é uma estrutura de dados de árvore binária, baseada em nós, 
onde todos os nós da subárvore esquerda possuem um valor numérico inferior ao nó 
raiz e todos os nós da subárvore direita possuem um valor superior ao nó raiz, com o 
objetivo de estruturar os dados de forma flexível, permitindo busca binária.” 
Com o conceito bem definido, vamos ao raciocínio para o algoritmo: 
Primeiro passo será criar a estrutura da arvore com a qual vamos trabalhar: 
Apresentação da minha estrutura: 
 
A estrutura é simples, e eu nomeei de arvore_bin por motivos óbvios. A estrutura 
define que cada nó da minha arvore vai ter no um inteiro info como identificador da 
chave, um ponteiro que aponta para a direita da minha arvore, outro que aponta para 
a esquerda. São estes ponteiros, em cada nó da arvore, que formarão o layout clássico 
arvore binária, no meu caso eu os nomeei com direita e esquerda para facilitar a 
leitura posterior. Criei também uma variável global com nome de raiz que vai apontar 
para o nó raiz da minha arvore. 
Implementado, ficou assim: 
 
 
2 
 
 
Um segundo ponto importante pra estruturação do programa é a interface do 
programa. 
Criei uma interface simples (tela preta) que exibe todas as funções disponíveis 
para o usuário. Tudo feito com um switch, onde o usuário digita o inteiro 
correspondente a cada função e o programa responde com a execução da função 
escolhida. 
Coloquei o switch dentro da função main, num loop que se repete até que o 
usuário pedir pra sair do loop. Dentro da função main, também coloquei uma 
atribuição de valor pra raiz, de modo que sempre que o programa começa, a raiz é 
setada pra NULL. 
Quando executado, o programa mostra a seguinte tela: 
 
 
Com a estrutura definida, e a base do programa feito, temos que começar a pensar 
em cada função exigida na proposta do TP. 
 
 Funçao INSERIR 
Começamos com a função inserir uma chave na arvore, que por definição está vazia! 
Voltando na definição de arvore binária, lembramos que para inserir um nó na arvore 
vamos ter três casos possíveis: 
 O primeiro nó a ser inserido (definido como a raiz). 
 Inserir um nó menor que a raiz. 
 Inserir um nó maior que a raiz. 
 
3 
 
Então criamos a função inserir e a configuramos como case 1 do switch (de acordo 
com o menu desenhado antes). 
A função recebe como parâmetros a raiz da arvore e o inteiro (chave) que se quer 
inserir na arvore. Capturando o inteiro por cin podemos começar a implementação da 
função. 
No caso da primeira inserção a raiz é comparada a NULL e a comparação retorna 
verdadeiro, então minha função já achou o lugar onde deve ser feita a inserção (na 
própria raiz), então ela vai chamar a função que cria o no onde vai ser inserida a chave 
int que o usuário digitou. A função gerar nó recebe como parâmetro o inteiro digitado 
pelo usuário para inserção. Então a função cria uma estrutura de arvore_bin, atribui o 
valor do inteiro digitado em info do nó (arvore_bin) criado e então atribui NULL para 
direita e esquerda do novo nó. Assim temos um nó folha pronto para ser inserido. 
Nesse momento a função retorna o ponteiro do novo nó folha. 
Após identificar a raiz como NULL, 
chamamos a função gerar_no passando o 
inteiro a ser inserido na arvore. 
 
No caso de uma inserção posterior (todas as próximas, depois de inserida a raiz), a 
mesma função de inserção vai receber o inteiro e comparar a raiz com NULL, como já 
inserimos um nó na raiz a comparação retorna falso e a função passa pra próxima 
condicional. Então já sabemos que a inserção é de um elemento que não é a raiz. 
Lembrando que a inserção em arvore binária segue o padrão de todas as chaves 
maiores que a raiz ficam a direita dela, e as chaves menores que a raiz ficam a 
esquerda. Vamos comparar o inteiro fornecido pelo usuário com o info da raiz, se a 
chave do usuário for maior que o info da raiz, chamamos inserção recursivamente 
passando o inteiro do usuário e um ponteiro para a sub arvore à direita da raiz, e caso 
a chave seja menor que o info da raiz chamamos a função inserção passando o inteiro 
fornecido pelo usuário acompanhado de um ponteiro para a sub arvore a esquerda da 
raiz. E assim o programa roda recursivamente até que chega em um ponto NULL, que 
seria o ponto da inserção. Então o inserção chama a função gerar_no pra alocar o novo 
nó, atribuir o valor do usuário ao info do novo nó e inserir o nó no NULL encontrado 
nas comparações de chaves. Ao completar a inserção, a função imprime uma 
mensagem de sucesso na inserção e retorna pra main. 
P.s: Se nesse ciclo de comparações, o programa achar uma info de um nó que seja 
igual ao inteiro digitado pelo usuário, a função mostra um alerta sobre a duplicação da 
inserção e retorna pra função main. Segue o corpo da função de inserção, bem como 
amostra de uma inserção sendo executada! 
 
4 
 
 
 No caso de a inserção ser bem sucedida o programa reage assim: 
 
 No caso de a inserção não ser bem sucedida o programa reage assim: 
 
 
5 
 
 
 Função PESQUISAR 
Sabemos qual é o procedimento para 
inserir, então automaticamente temos 
explicito a lógica de busca, já que antes de 
inserir temos que fazer a busca. 
Então a função pesquisar vai seguir os 
mesmos passos da inserção, com o porém 
de que ela recebe o inteiro o qual se deseja 
pesquisar seguido da raiz da arvore e 
apenas imprime uma mensagem informando o resultado da busca. 
Em mais detalhes, a função pesquisa tem um comparativo do inteiro inserido pelo 
usuário com a info de cada nó por meio da recursividade da própria função. Então 
aplicando temos três casos: 
Seja x o inteiro digitado pelo usuário e info o inteiro que é armazenado em cada nó 
da arvore. A pesquisa compara x com info, e se o valor dos dois for igual, a função 
imprime a mensagem “ ’X’ está na arvore”. 
 Caso X seja maior que info, a função chema a si própria passando x e um 
ponteiro para a subarvore a direita. 
 caso x seja menor que info a função chama a si própria passando x e um 
ponteiro pra subarvore a esquerda. Até achar a chave pesquisada. 
 Caso a arvore tenha sido totalmente percorrida e o valor da ultima pesquisa foi 
NULL então imprima uma mensagem informando que o numero não esta na 
arvore. 
Segue a apresentação dois retornos possiveis em casos de busca.: 
Busca retorna POSITIVO! 
 
 
6 
 
Busca retorna NEGATIVO! 
 
 
 Função ORDENAR 
A função ordenar recebe a raiz da 
arvore como parâmetro e retorna a exibição 
de todos os nós da arvore em ordem 
crescente. A função também é conhecida por 
caminhamento e é bastante popular e de 
simples implementação. 
A partir da raiz da arvore, a função cria uma condicional, se o ponteiro o aponta 
pra algo diferente de NULL então chame a própria função recursivamente passando 
um ponteiro pra sub arvore a esquerda, imprima o nó a esquerda, e depois chame a 
própria função recursivamente de novo passando um ponteiro pra sub arvore adireita. Quando terminar de percorrer toda a arvore, o ponteiro aponta para NULL e a 
função retorna para main. 
 
 
7 
 
 Função REMOVER 
 
 A função de remoção numa arvore binária, pode ser considerada um pouco 
mais complexa. Devido as propriedades de remoção em arvore binária. Ou seja, temos 
um caso diferente para um nó que tem 0, 1 ou 2 filhos. Alem de remover o nó com a 
chave inserida, a função deve alocar outro nó no espaço do antigo (quando não é nó 
folha). 
 Então fazendo um passo a passo a função pode ser dividida em algumas ‘etapas’: 
 A função recebe um ponteiro para a raiz da arvore, e o inteiro (fornecido pelo 
usuário) que se quer remover da arvore. A partir de então podemos criar 5 novos 
ponteiros. São eles: 
REM – vai apontar para o nó a ser removido (mas inicializa a função 
apontando para raiz) 
PAI_R – apontar para o pai do nó a ser removido 
SUBST - apontar para o nó substituto do removido 
PAI_S - Vai apontar para o pai do nó substituto o removido 
FILHO_S - Vai apontar para o filho a esquerda do nó substituto o 
removido 
Vamos ter uma repetição de pesquisa de chave. Vamos comparar o inteiro 
fornecido pelo usuário à chave info do nó que REM aponta, e se for diferentes o 
ponteiro pai_r vai passar a apontar pra REM, enqnt vamos comparar info de REM de 
novo pra saber pra qual arvore devemos seguir buscando. Seja, se info de REM for 
maior que o inteiro fornecido pelo usuário, então REM passa a apontar para a 
subarvore a esquerda de REM próprio, se for menor que o inteiro, então REM passa a 
apontar ppra direita de REM próprio. Se a busca terminar e retornar um ponteiro para 
o valor do inteiro quer dizer que o valor que se deseja remover ainda nem foi inserido 
na arvore. Nesse caso imprime mensagem de erro e retorna. 
 
 
8 
 
 
Salvo esse caso de o valor não estar presente na arvore, o fim do loop anterior 
vai retornar o nó que contem a chave buscada, ou seja, ele é que será removido. Mas 
como vamos saber se podemos apagar ele antes de saber dos filhos ? 
Então fazemos uma nova condicional para cada caso, os quais eu vou reduzir um 
pouco devido ao maior grau de abstração nas operações com ponteiros. (Mas com 
certeza já falei e apresentei em sala com apoio de papel se preciso.) 
Se o nó a ser removido tem apenas um filho, o ponteiro SUBST caminha pela 
subarvore do nó até o nó a esquerda, ou direita em cada caso. Depois, no fim da 
função, atribuímos SUBST a sub arvore de PAI_R que teve seu filho removido. Temos 
uma condicional para isso, se REM for filho esquerdo de PAI_R então SUBST e alocado 
a esquerda de PAI_R , do contrario SUBST e alocado a direita de PAI_R e a função da 
um free em REM e retorna SUBST depois de avisar que obteve sucesso. 
Se o nó apontado por REM tem dois filhos, então vamos atribuir o endereço de 
REM pro PAI_R e vamos caminhar com SUBST para a direita de REM e atribuir a 
FILHO_S o endereço da sub arvore a esquerda de SUBST. A partir de então criamos um 
novo laço condicional que funciona enquanto FILHO_S ainda não aponta pra NULL, a 
cada execução todos os ponteiros descem uma sub arvore a esquerda. Quando 
FILHO_S aponta pra NULL é sinal de que SUBST já está no nó sucessor de REM, então 
para a repetição e vai pra próxima condicional. Se o nó substituto de REM tiver algum 
filho ou sub arvore a sua direita, essa será alocada a esquerda de PAI_S, senão o 
ponteiro esquerdo de PAI_S recebe NULL. O nó substituto de REM recebe a sub arvore 
da direita de REM sendo alocada em sua sub arvore da direita, e a sub arvore da 
esquerda de REM passa a ser a sub arvore a esquerda de SUBST. Então remove REM e 
imprime uma mensagem de sucesso antes de retornar SUBST. Dessa forma, o no a ser 
removido, vai ser substituído antes pelo seu sucessor, que será nada diferente do que 
o elemento mais a esquerda de sua sub arvore direita. 
E para o caso de REM não ter nenhum nó, nós apenas o removemos sem ter 
que ter substituição alguma. É o caso da próxima função implementada. 
 
Caso de sucesso de uma remoção 
 
9 
 
 Função REMOVER FOLHAS 
 
Bom, após tantas operações prontas, a remoção apenas das folhas se 
tornou algo trivial, já que já implementamos as funções de pesquisar e de 
remover, logo, se unirmos as duas teremos a implementação da função de 
remoção de folhas. 
 
A função recebe apenas um ponteiro pra raiz da arvore. Ela remove 
todos os nós folha presentes na arvore, e apresenta a listagem dos nós 
removidos. Declaramos uma aux apenas para fins de retorno da função de 
modo que consigamos criar o laço de repetição corretamente. 
A função é muito simples e funciona assim: 
Se o ponteiro aponta para um ponteiro cujos filhos direito E esquerdo são 
NULL, então entra no laço e pega o info desse nó e passa como parametro 
(junto com a raiz da arvore) para a função remoção, assim a função remoção 
busca o nó cuja chave é o inteiro presente no nó atual e o remove, imprime a 
mensagem de sucesso e retorna aux. Então temos outras condicionais para 
fazer o ponteiro da função percorrer toda a arvore. Funciona assim, se a sub 
arvore da esquerda do ponteiro é diferente de NULL, então chama a própria 
função recursivamente, passando o ponteiro apontando para a esquerda do nó 
 
10 
 
atual. Ou a mesma lógica caso a sub arvore da direita de nó atual seja diferente 
de NULL. Ou seja, chama a função recursivamente passando um ponteiro pra 
sub arvore da direita do nó atual. 
P.s.:Como raiz é uma variável global, eu criei uma condicional para atribuir 
valor à raiz com o retorno da função remove, porque assim o valor de raiz é atualizado 
impedindo de termos qualquer problema nas próximas operações. Aliás, essa mesma 
condicional é imposta na função remoção assim que obtemos o valor que se deseja 
remover, já que temos os mesmos motivos para tal. 
Segue ilustração de um teste de sucesso com uma arvore que tinha quatro nós folhas: 
 
 
 
 Função VERIFICAÇÂO BALANCEAMENTO 
 
 
A função balanceamento é composta por duas funções. A função verificação 
recebe a raiz da arvore binária, e La dentro da função verificação é chamada a função 
Altura passando a raiz como parâmetro enquanto a função altura retornna para a 
função verificação a altura de cada subarvore, a função verificação calcula a diferença 
entre as alturas e verifica se é maior que 1 ou menor que -1. Se for imprime a 
mensagem avisando que esta desbalanceada. 
 
 
 
11 
 
Referencias: 
 
pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria_de_busca 
paginas.fe.up.pt/~arocha/AED/APONTS/arvores.pdf 
www.inf.puc-rio.br/~inf1007/.../arvoresbinarias.pdf 
edaii.wordpress.com 
ime.usp.br/~pf/mac0122-2002/aulas/trees.html 
 
12 
 
 
 
 
ANEXO 
(Código Fonte)