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;
}
O resultado de sua execução deve ser este: 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 !
| versão alternativa do programa de teste
|
#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 = nullptr;
for (auto & fruta : w) {
if (arv) arv->adiciona(fruta);
else arv = new arvore<string>(fruta);
}
for (auto & fruta : w) {
try {
cout << "arv[" << fruta << "] = " << arv->obtem(fruta) << endl;
} catch (...) {
cout << "Ops: " << fruta << " não está na árvore !" << endl;
}
}
delete arv;
return 0;
}
|
|
- 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 |
| Animação
|
 |}
|
| Pre order |
visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore |
| Animação
|
 |}
|
| Post order |
visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz |
| Animação
|
 |}
|
| Level order |
visitam-se nodos cada nível por vez, da esquerda pra direita |
| Animação
|
 |}
|
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.
void listeInOrder(lista<T> & result);
void listePreOrder(lista<T> & result);
void listePostOrder(lista<T> & result);
void listeEmLargura(lista<T> & result);
| 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.
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
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
}
}
|
As versões não-recursivas desses algoritmos podem ser facilmente encontradas em forums de programadores, e também na Wikipedia:
Iteração da árvore
A iteraçao da árvore na 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:
| Declaração da arvore em libs/arvore.h contendo o atributo para a pilha
|
#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 */
|
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:
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
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)
|
|
|
|
