Mudanças entre as edições de "PRG29003: A implementação da árvore de pesquisa binária"
(Criou página com '__toc__ No projeto 4 estudaram-se árvores de pesquisa binária como forma de acesso rápido a dados armazenados. Usou-se então ...') |
|||
Linha 70: | Linha 70: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | = Atividade = | + | == Atividade == |
'''OBS:''' O programa abaixo pode ser usado como um testador inicial da implementação da árvore: | '''OBS:''' O programa abaixo pode ser usado como um testador inicial da implementação da árvore: | ||
Linha 214: | Linha 214: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
+ | |||
+ | = Enumerando os dados de uma árvore = | ||
+ | |||
+ | |||
+ | Até o momento nos concentramos em operações básicas de árvores. Elas possibilitam criar e adicionar dados a uma árvore, e pesquisar por um dado em função de um dado específico. Porém outras formas de acessar os dados de uma árvore podem ser úteis, dentre elas o acesso sequencial de acordo com uma determinada ordem. Por exemplo, pode-se desejar acessar os dados de uma árvore de forma ordenada. Assim, devem-se conhecer as quatro ordens de visitação de nodos de uma árvore: | ||
+ | <!--* '''In order:''' visitam-se nodos na sequência esquerda, raiz, direita. O resultado é o acesso ordenado em função das chaves. | ||
+ | * '''Pre order:''' visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore. | ||
+ | * '''Post order:''' visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz. | ||
+ | * '''Level order:''' visitam-se nodos cada nível por vez, da esquerda pra direita. | ||
+ | --> | ||
+ | |||
+ | {| border=1 | ||
+ | !Tipo | ||
+ | !Descrição | ||
+ | !Exemplo | ||
+ | |- | ||
+ | |'''In order'''||visitam-se nodos na sequência esquerda, raiz, direita. O resultado é o acesso ordenado em função das chaves||{{collapse top|Animação}}[[imagem:Prg2-Inorder.gif]]{{collapse bottom}} | ||
+ | |- | ||
+ | |'''Pre order''' ||visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore||{{collapse top|Animação}}[[imagem:Prg2-Preorder.gif]]{{collapse bottom}} | ||
+ | |- | ||
+ | |'''Post order''' ||visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz||{{collapse top|Animação}}[[imagem:Prg2-Postorder.gif]]{{collapse bottom}} | ||
+ | |- | ||
+ | |'''Level order'''|| visitam-se nodos cada nível por vez, da esquerda pra direita||{{collapse top|Animação}}[[imagem:Prg2-Levelorder.gif]]{{collapse bottom}} | ||
+ | |} | ||
+ | |||
+ | As três primeiras formas de acesso são do tipo '''busca em profundidade''', pois implicam descer até as folhas de um lado antes de visitarem o outro lado da árvore. A última forma de acesso é do tipo '''busca em largura''', pois os nodos são visitados por nível da árvore. | ||
+ | |||
+ | |||
+ | Cada uma das formas de acesso tem sua aplicações em algoritmos. Por exemplo, ''in order'' serve para ordenar os dados, ''pre order'' pode ser usada para copiar uma árvore, e ''post order'' pode ser usado para destruir uma árvore. Alguns algoritmos já criados usam algumas dessas formas de acesso (ex: ''escrevaSe'' é do tipo ''in order''; o destrutor da árvore e ''altura'' são do tipo ''post order''). Hoje será visto como implementar métodos genéricos que enumeram os dados de uma árvore segundo essas sequências de acesso. | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | void listeInOrder(lista<T> & result); | ||
+ | void listePreOrder(lista<T> & result); | ||
+ | void listePostOrder(lista<T> & result); | ||
+ | void listeEmLargura(lista<T> & result); | ||
+ | </syntaxhighlight>''Os métodos de enumeração na classe arvore'' | ||
+ | |||
+ | {{collapse top | um algoritmo para listePreOrder em versão não-recursiva}} | ||
+ | A versão não-recursiva de listePreOrder precisa de uma pilha para navegar pelos nodos da árvore. | ||
+ | |||
+ | <syntaxhighlight lang=text> | ||
+ | algoritmo PRE_ORDER: | ||
+ | empilha raiz | ||
+ | |||
+ | enquanto pilha não vazia faça | ||
+ | desempilha um nodo | ||
+ | faz algo com nodo | ||
+ | |||
+ | se nodo tem ramo direito então empilha ramo direito | ||
+ | se nodo tem ramo esquerdo então empilha ramo esquerdo | ||
+ | fim enquanto | ||
+ | |||
+ | fim algoritmo | ||
+ | </syntaxhighlight>''Algoritmo em pseudo-código'' | ||
+ | |||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | template <typename T> void arvore<T>::listePreOrder(lista<T> & result) { | ||
+ | // OBS: com a lista funcionando como pilha, | ||
+ | // push <==> insere(algo), pop <==> remove(0) | ||
+ | lista<arvore<T>*> q; // pilha de nodos a visitar | ||
+ | |||
+ | q.insere(this); // inicia com a raiz | ||
+ | while (not q.vazia()) { // repete até que pilha fique vazia | ||
+ | // desempilha um nodo | ||
+ | // anexa em result dado do nodo desempilhado | ||
+ | // se nodo tem ramo direito, empilha-o | ||
+ | // se nodo tem ramo esquerdo, empilha-o | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight>''Esqueleto do método listePreOrder em versão não-recursiva'' | ||
+ | {{collapse bottom}} | ||
+ | |||
+ | |||
+ | As versões não-recursivas desses algoritmos podem ser facilmente encontradas em forums de programadores, e também na [http://www.wikipedia.org/ Wikipedia]: | ||
+ | * [https://en.wikipedia.org/wiki/Tree_traversal#In-order_2 In-order] | ||
+ | * [https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_2 Pre-order] | ||
+ | * [https://en.wikipedia.org/wiki/Tree_traversal#Post-order_2 Post-order] | ||
+ | * [https://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_search_2 Em-largura] | ||
+ | |||
+ | == Iteração da árvore == | ||
+ | |||
+ | A iteraçao da árvore na [[PRG2-2017-2#A_.C3.A1rvore_de_pesquisa_bin.C3.A1ria_da_prglib|Prglib original]] possibilita obter de forma ordenada os dados contidos na árvore. Assim, a iteração segue uma enumeração dos dados no estilo ''in-order''. Para implementá-la deve-se usar um algoritmo não-recursivo, visto que cada chamada do iterador, por meio do método ''proximo'', retorna um único dado. | ||
+ | |||
+ | |||
+ | Um algoritmo para enumeração ''in-order'' faz uso de uma pilha como estrutura de dados auxiliar. Sendo assim, a ''classe arvore'' precisa possuir uma pilha como um novo atributo. Para economizar memória, já que todo nodo da árvore possuirá esse novo atributo, a pilha deve ser criada dinamicamente quando se inicia uma iteração, e destruída ao final da iteração. Para isso a pilha deve ser declarada como o ponteiro ''p_stack'' na ''classe arvore'': | ||
+ | |||
+ | {{collapse top|Declaração da arvore em libs/arvore.h contendo o atributo para a pilha}} | ||
+ | <syntaxhighlight lang=c> | ||
+ | #ifndef ARVORE_H | ||
+ | #define ARVORE_H | ||
+ | |||
+ | namespace prglib { | ||
+ | |||
+ | template <typename T> class arvore { | ||
+ | public: | ||
+ | arvore(); | ||
+ | //arvore(const arvore<T> & outra); | ||
+ | arvore(const T & dado); | ||
+ | virtual ~arvore(); | ||
+ | |||
+ | void adiciona(const T& algo); | ||
+ | T& obtem(const T & algo); | ||
+ | void listeInOrder(lista<T> & result); | ||
+ | void listePreOrder(lista<T> & result); | ||
+ | void listePostOrder(lista<T> & result); | ||
+ | void listeEmLargura(lista<T> & result); | ||
+ | unsigned int tamanho() const; | ||
+ | unsigned int altura() ; | ||
+ | int fatorB() ; | ||
+ | arvore<T> * balanceia(); | ||
+ | arvore<T> * balanceia(bool otimo); | ||
+ | |||
+ | // iterador in-order | ||
+ | void inicia(); | ||
+ | bool fim(); | ||
+ | T& proximo(); | ||
+ | |||
+ | // iterador in-order reverso | ||
+ | void iniciaPeloFim(); | ||
+ | bool inicio(); | ||
+ | T& anterior(); | ||
+ | |||
+ | // remove um dado equivalente a "algo", retornando uma cópia | ||
+ | T remove(const T & algo); | ||
+ | |||
+ | // obtém maior ou menor dados contidos na árvore | ||
+ | T & obtemMenor() const; | ||
+ | T & obtemMaior() const; | ||
+ | |||
+ | void obtemMenoresQue(lista<T> & result, const T & algo); | ||
+ | void obtemMaioresQue(lista<T> & result, const T & algo); | ||
+ | |||
+ | // obtém todos valores entre "start" e "end" (inclusive) | ||
+ | void obtemIntervalo(lista<T> & result, const T & start, const T & end); | ||
+ | protected: | ||
+ | T data; | ||
+ | arvore<T> * esq, * dir; | ||
+ | |||
+ | // um ponteiro para pilha a ser usada pelo iterador. | ||
+ | // OBS: pode-se usar uma lista como se fosse pilha ! | ||
+ | lista<arvore<T>*> * p_stack; | ||
+ | |||
+ | arvore<T> * rotacionaL(); | ||
+ | arvore<T> * rotacionaR(); | ||
+ | }; | ||
+ | |||
+ | } // fim do namespace | ||
+ | |||
+ | #include <libs/arvore-impl.h> | ||
+ | |||
+ | #endif /* ARVORE_H */ | ||
+ | </syntaxhighlight> | ||
+ | {{collapse bottom}} | ||
+ | |||
+ | |||
+ | O algoritmo para enumeração ''in-order'' é mostrado a seguir. Deve-se notar que esse algoritmo enumera todos os dados da árvore. Portanto, ele é uma versão não-recursiva de ''listeInOrder'': | ||
+ | |||
+ | <syntaxhighlight lang=text> | ||
+ | algoritmo in-order(lista): | ||
+ | cria uma pilha de nodos | ||
+ | |||
+ | empilha a raiz e todos os nodos nos ramos mais à esquerda da raiz, | ||
+ | até o nodo com menor valor | ||
+ | enquanto pilha não vazia faça | ||
+ | desempilha um nodo | ||
+ | anexa à lista dado do nodo | ||
+ | se nodo possui ramo direito então | ||
+ | empilha o nodo direito e todos os nodos nos ramos mais à esquerda dele, | ||
+ | até o nodo com menor valor | ||
+ | fim se | ||
+ | fim enquanto | ||
+ | |||
+ | destroi pilha | ||
+ | |||
+ | fim in-order | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | A iteração da árvore pode aproveitar esse algoritmo com pequenas modificações. | ||
+ | |||
+ | == Atividade == | ||
+ | |||
+ | # Implemente a iteração in-order de sua árvore (métodos ''inicia, proximo, fim'') | ||
+ | # Implemente a iteração in-order reversa de sua árvore (métodos ''iniciaPeloFim, anterior, inicio'') |
Edição das 07h39min de 15 de junho de 2018
No projeto 4 estudaram-se árvores de pesquisa binária como forma de acesso rápido a dados armazenados. Usou-se então uma implementação de árvore fornecida na prglib. Agora deve-se implementar essa estrutura de dados para que ofereça as mesmas operações existentes na prglib original.
Começando uma árvore binária
A árvore de pesquisa binária é formada por nodos que armazenam um dado qualquer (da mesma forma que foi feito com listas), e possui no máximo dois ramos. O ponto de partida pode ser visto na primeira versão do arquivo libs/arvore.h, mostrada abaixo:
#ifndef ARVORE_H
#define ARVORE_H
namespace prglib {
template <typename T> class arvore {
public:
arvore();
//arvore(const arvore<T> & outra);
arvore(const T & dado);
~arvore();
void adiciona(const T& algo);
const T& obtem(const T & algo);
void listeInOrder(lista<T> & result);
void listePreOrder(lista<T> & result);
void listePostOrder(lista<T> & result);
void listeEmLargura(lista<T> & result);
unsigned int tamanho() const;
unsigned int altura() ;
int fatorB() ;
arvore<T> * balanceia();
arvore<T> * balanceia(bool otimo);
// iterador in-order
void inicia();
bool fim();
const T& proximo();
// iterador in-order reverso
void iniciaPeloFim();
bool inicio();
const T& anterior();
// remove um dado equivalente a "algo", retornando uma cópia
T remove(const T & algo);
// obtém maior ou menor dados contidos na árvore
const T & obtemMenor() const;
const T & obtemMaior() const;
void obtemMenoresQue(lista<T> & result, const T & algo);
void obtemMaioresQue(lista<T> & result, const T & algo);
// obtém todos valores entre "start" e "end" (inclusive)
void obtemIntervalo(lista<T> & result, const T & start, const T & end);
protected:
T data;
arvore<T> * esq, * dir;
// operações internas usadas pelo balanceamento
arvore<T> * rotacionaL();
arvore<T> * rotacionaR();
};
} // fim do namespace
#include <libs/arvore-impl.h>
#endif /* ARVORE_H */
Atividade
OBS: O programa abaixo pode ser usado como um testador inicial da implementação da árvore:
Programa de teste da árvore | ||
---|---|---|
#include <iostream>
#include <string>
#include <prglib.h>
using namespace std;
using prglib::arvore;
int main() {
string w[7] = {"graviola","caju","sapoti","acai", "banana","morango","laranja"};
// Uma árvore deve ser criada dinamicamente ... isso facilita
// sua implementação.
arvore<string> * arv = new arvore<string>(w[0]);
for (int n=1; n < 6; n++) arv->adiciona(w[n]);
for (int n=0; n < 7; n++) {
try {
cout << "arv[" << w[n] << "] = " << arv->obtem(w[n]) << endl;
} catch (...) {
cout << "Ops: " << w[n] << " não está na árvore !" << endl;
}
}
delete arv;
return 0;
}
arv[graviola] = graviola
arv[caju] = caju
arv[sapoti] = sapoti
arv[acai] = acai
arv[banana] = banana
arv[morango] = morango
Ops: laranja não está na árvore !
|
- Implemente adiciona e obtem de forma não-recursiva. Nessa versão, esses métodos usam um laço para percorrer os nodos da árvore.
<syntaxhighlight lang=text> algoritmo adiciona(algo): Define raiz como nodo atual Para sempre faça se algo igual ao dado do nodo atual então substitui dado do nodo atual por algo termina algoritmo fimSe se algo menor que dado do nodo atual então se existe ramo esquerdo então nodo atual é o nodo da esquerda senão cria novo nodo com algo conecta o novo nodo no ramo esquerdo termina algoritmo fimSe senão se existe ramo direito então nodo atual é o nodo da direita senão cria novo nodo com algo conecta o novo nodo no ramo direito termina algoritmo fimSe fimSe fimPara fim adiciona
- Como exercício, implemente adiciona e obtem de forma recursiva. Nessa versão, esses métodos NÃO usam um laço para percorrer os nodos da árvore. Dica: note que cada ramo de uma árvore pode ser visto como uma outra árvore. Esses métodos são parecidos, e o seguinte pseudo-código ilustra o método adiciona em uma versão não-recursiva:
algoritmo adiciona(algo): se algo igual ao dado da raiz então substitui dado da raiz por algo termina algoritmo fimSe se algo menor que dado da raiz então se existe ramo esquerdo então adiciona algo na subárvore da esquerda senão cria novo nodo com algo conecta o novo nodo no ramo esquerdo termina algoritmo fimSe senão se existe ramo direito então adiciona algo na subárvore da direita senão cria novo nodo com algo conecta o novo nodo no ramo direito termina algoritmo fimSe fimSe fimPara fim adiciona
- Implemente os métodos obtemMenor e obtemMaior. Eles são bem simples ...
- Implemente o método altura ... faça-o de forma recursiva, pois a versão não-recursiva não é fácil ! A altura da árvore é uma informação importante relacionada à eficiência na estrutura da árvore (sua topologia), como visto lá numa seção do projeto 4. Como visto, a altura de uma árvore A pode ser calculada com esta recorrência:
Enumerando os dados de uma árvore
Até o momento nos concentramos em operações básicas de árvores. Elas possibilitam criar e adicionar dados a uma árvore, e pesquisar por um dado em função de um dado específico. Porém outras formas de acessar os dados de uma árvore podem ser úteis, dentre elas o acesso sequencial de acordo com uma determinada ordem. Por exemplo, pode-se desejar acessar os dados de uma árvore de forma ordenada. Assim, devem-se conhecer as quatro ordens de visitação de nodos de uma árvore:
Tipo | Descrição | Exemplo | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
In order | visitam-se nodos na sequência esquerda, raiz, direita. O resultado é o acesso ordenado em função das chaves |
|