aula04

Prévia do material em texto

4ºAula
ÁRVORES DE BUSCA BINÁRIA – 
PARTE I
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
• conhecer o que são árvores de busca binária;
• aprender os diferentes tipos de percursos que podem ser feitos em uma ABB;
• saber como fazer uma busca em uma ABB.
Olá,
Nesta aula, vamos começar os estudos da Árvore de Busca 
Binária (ABB), uma das estruturas de dados mais elementares 
da área da Computação. Nesta quarta aula, vamos saber o que 
são as árvores de busca binária, e como buscar dados nessa 
estrutura de dados, entre outros aspectos importantes.
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!
27
Estrutura de Dados II 26
1. 
Seções de estudo
Introdução às Árvores de Busca Binária
2. Percursos em ABB
3. Busca em uma ABB
1 -Introdução às Árvores de Busca 
Binária
Na aula anterior, vimos as Árvores Binárias, que são 
árvores em que o número de filhos de cada nó é menor ou 
igual a dois. As árvores de busca binária seguem as regras de 
uma árvore binária, mas possuem regras próprias, visando a 
otimizar o processo de busca dos dados. As regras se aplicam 
explicitamente na hora da inserção dos dados, que são:
• Se a árvore é vazia, o dado é inserido na raiz da 
árvore.
• Uma vez a árvore com uma raiz, os dados 
subsequentes são inseridos obedecendo a seguinte 
regra: Se for menor que o elemento da raiz é inserido 
na subárvore esquerda. Se for maior é inserido na 
subárvore direita do nó.
Assim, as árvores de busca binária são árvores binárias, 
que possuem uma disciplina de organização dos dados. Para 
procurarmos um dado basta começarmos da raiz. Se o que 
estivermos procurando é menor que a raiz, continuamos a 
busca no seu filho esquerdo. Se o que estivermos procurando 
é maior que a raiz, continuamos a busca no seu filho direito. 
Na imagem a seguir mostramos uma árvore de busca 
binária.
Acervo Pessoal.
Observem a disposição dos elementos da árvore, que 
segue as regras que explicamos aqui. Aproveitem a ilustração 
para tentar simular mentalmente como buscar um dado na 
árvore. Ainda nesta aula, vamos abordar o processo de busca 
em uma árvore binária.
Aliás, a busca é uma das formas de processamento em 
uma árvore binária. Como nas listas, temos uma série de 
algoritmos que realizam uma série de processamentos em 
uma árvore binária. Vamos ver alguns deles:
• Visitação (Percorrer) todos os nós da árvore.
• Procurar um nó na árvore.
• Inserir um nó na árvore.
• Remover um nó na árvore. 
• Entre outros.
Nas próximas seções desta aula e da próxima aula, vamos 
discutir os algoritmos de processamento que se aplicam em 
árvores de busca binárias. Mas, antes cabe aqui mais um 
esclarecimento. Alguns dos algoritmos mostrados usaram 
uma função auxiliar chamada VisitaNo, que consiste apenas 
em escrever o valor do nó que foi passado como parâmetro. 
Vamos ao pseudocódigo.
procedimento VisitaNo(Atual: *TArvore)
início
 escreva(Atual->dado)
fimprocedimento
Agora, com esse procedimento auxiliar apresentado, 
vamos mostrar como percorrer os nós em uma árvore de 
busca binária.
2 -Percursos em ABB
Os percursos são algoritmos cuja função é percorrer 
todos os nós da árvore. Como há uma série de possibilidades 
de qual nó escolher para iniciar um percurso em uma árvore 
binária, os pesquisadores desenvolveram três formas de se 
fazer um percurso. A diferença nesses percursos é a ordem 
pela qual os nós são visitados. Todos os algoritmos 
apresentados são recursivos. Vamos a eles:
2.1 - Percurso Pré-Ordem
O percurso pré-ordem segue os seguintes passos:
1. Visita o nó.
2. Percorre recursivamente a subárvore esquerda.
3. Percorre recursivamente a subárvore direita.
 Assim, o primeiro nó a ser visitado é a raiz da árvore. 
Depois, será visitado os nós da subárvore esquerda, sempre 
priorizando a raiz da subárvore naquele instante. A seguir, a 
ordem de visitação dos nós em um percurso pré-ordem:
Figura 2 - Percurso Pré-Ordem. Fonte: Acervo Pessoal.
A seguir, o pseudocódigo do percurso pré-ordem:
procedimento preOrdem(Raiz: *TArvore)
 se (Raiz NULO) entao
 VisitaNo(Raiz)
 preOrdem(Raiz->esq)
 preOrdem(Raiz->dir)
 fimse
fimprocedimento
28
27
2.2 - Percurso Pós-Ordem
É um percurso que segue os seguintes passos:
1. Percorre recursivamente a subárvore esquerda.
2. Percorre recursivamente a subárvore direita.
3. Visita o Nó.
Assim, primeiro percorremos toda a subárvore esquerda, 
em seguida toda a subárvore direita. Após fazermos isso, 
visitamos a raiz. A seguir, mostraremos como funcionaria a 
ordem dos elementos apresentados em uma subárvore, em 
um percurso pré-ordem.
Figura 3 - Percurso Pós-Ordem. Fonte: Acervo Pessoal.
 
A seguir, o pseudocódigo do percurso pós-ordem:
procedimento posOrdem(Raiz: *TArvore)
 se (Raiz NULO) entao
 posOrdem(Raiz->esq)
 posOrdem(Raiz->dir)
 VisitaNo(Raiz)
 fimse
fimprocedimento
2.3 - Percurso In-Ordem
Por último, temos o percurso In-Ordem que consiste 
nos seguintes passos:
1. Percorre a subárvore esquerda recursivamente.
2. Visita o nó raiz.
3. Percorre a subárvore direita recursivamente.
Agora, vamos mostrar o resultado de um percurso in-
ordem em uma árvore.
Figura 4 - Percurso Pós-Ordem. Fonte: Acervo Pessoal.
Perceba que os elementos são percorridos na ordem 
crescente. Assim, se quisermos obter os elementos de forma 
ordenada, devemos executar esse algoritmo. A seguir, o 
pseudocódigo do percurso in-ordem:
procedimento inOrdem(Raiz: *TArvore)
 se (Raiz NULO) entao
 inOrdem(Raiz->esq)
 VisitaNo(Raiz)
 inOrdem(Raiz->dir)
 fimse
fimprocedimento
Na próxima seção, mostraremos como funciona o 
processo de busca em uma árvore de busca binária.
3 -Busca em uma ABB
Na Seção I, desafiamos vocês a simular como buscaria 
um dado em uma árvore de busca binária. Se vocês 
conseguiram, parabéns! Se não, não se preocupe. Vamos ver 
como funciona o processo de busca em uma árvore binária. 
Mas antes, vamos ver mais uma vez a nossa árvore de exemplo:
Bem, nós falamos que os elementos são inseridos da 
seguinte forma: Caso o elemento é menor que o valor da raiz, 
ele é inserido à esquerda. Se for maior, ele é inserido à direita.
Suponhamos que você queira buscar o valor 21. Vamos 
simular como funcionaria a busca:
• A busca sempre começa pela raiz. Assim, vamos 
ver se 21 é igual a 30. Como não é, vemos se 21 é 
maior ou menor que 30. Como ele é menor, vamos 
percorrer a subárvore esquerda.
• O próximo elemento a ser comparado é o 13. Como 
não é igual a 21, verificamos se 21 é menor ou maior 
que 13. Como é maior, percorremos a subárvore 
direita.
• A seguir, veremos o valor 17. Como ainda não é igual 
ao número que estamos procurando, verificamos 
se 21 é maior ou menor que 17. Como é maior, 
percorremos a subárvore direita.
• Finalmente, encontramos o valor 21.
Assim, temos um processo de busca para uma árvore de 
29
Estrutura de Dados II 28
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
busca binária, que há alguma semelhança com a busca binária, 
mas com a diferença de não precisarmos dividir o vetor, pois 
a hierarquia dos elementos em uma árvore de busca binária 
facilita isso.
A seguir, vamos apresentar o pseudocódigo deste 
algoritmo de busca.
funcao buscaABB(Raiz: *TArvore, chave: 
inteiro) : *TArvore
inicio
 se (RaizNULO) entao
 enquanto ( (Raiz->dado chave) e 
(Raiz NULO) faca
 se (chave < Raiz->dado) entao
 Raiz <- (Raiz->esq)
 senao
 Raiz <- (Raiz->dir)
 fimse
 fimenquanto
 fimse
 retorne Raiz
fimfuncao
Dete minando o meno e o maio alo em ma o e de 
sca in ia
Sabendo que os elementos menores são inseridos a esquerda 
da árvore, e que os elementos maiores são inseridos a direita da 
árvore, podemos entender que o menor elemento da árvore pode 
ser encontrado se percorrermos recursivamente a esquerda, até 
que não se encontre mais elementos. E para encontrarmos o maior 
elemento da árvore, percorremos recursivamente a direita, até o 
último elemento da árvore.
A seguir, apresentaremos os algoritmos
procedimento minimo(Raiz: *TArvore)
inicio
 enquanto (Raiz->esq NULO)
 Raiz <- (Raiz->esq)
 menquanto
 retorne Raiz
 mprocedimento
procedimento maximo(Raiz: *TArvo-
re)
inicio
 enquanto (Raiz->dir NULO)
 Raiz <- (Raiz->dir)
 menquanto
 retorne Raiz
 mprocedimento
E com isso, finalizamos a nossa aula. Na próxima aula, 
vamos estudar como funciona o processo de inserção e 
remoção de elementos em uma árvore de busca binária.
Retomando a aula
Chegamos ao nal da nossa quarta aula. Vamos 
relembrar os pontos principais?
1 - Introdução às Árvores de Busca Binária
Nesta seção, vimos que as árvores de busca binária são 
árvores binárias, que possuem uma disciplina de organização 
dos dados. Para procurarmos um dado, basta começarmos 
da raiz. Se o que estivermos procurando é menor que a 
raiz, continuamos a busca no seu filho esquerdo. Se o que 
estivermos procurando é maior que a raiz, continuamos a 
busca no seu filho direito. 
2 - Percursos em ABB
Nesta seção, vimos como percorrer os elementos de uma 
árvore de busca binária. Existem três percursos: Pré-ordem, 
Pós-Ordem e In-Ordem. Lembrando que em um percurso 
in-Ordem, obtemos a sequência ordenada de elementos da 
árvore de busca binária.
3 - Busca em uma ABB
Nesta seção, estudamos como funciona o algoritmo 
de busca em uma árvore de busca binária. Ela segue os 
fundamentos da árvore de busca binária, percorrendo a direita 
ou a esquerda, de acordo com o valor do elemento que está 
sendo percorrido. 
30
29
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
31