Baixe o app para aproveitar ainda mais
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
Compartilhar