Mudanças entre as edições de "PRG29003: A implementação da árvore de pesquisa binária"
Linha 10: | Linha 10: | ||
#ifndef ARVORE_H | #ifndef ARVORE_H | ||
#define ARVORE_H | #define ARVORE_H | ||
+ | |||
+ | #include <istream> | ||
+ | #include <string> | ||
+ | |||
+ | using std::string; | ||
+ | using std::istream; | ||
namespace prglib { | namespace prglib { | ||
Linha 15: | Linha 21: | ||
template <typename T> class arvore { | template <typename T> class arvore { | ||
public: | public: | ||
+ | // este construtor na prática não deve ser usado ... | ||
arvore(); | arvore(); | ||
− | // | + | |
+ | // cria um nodo da árvore, o qual contém o dado passado no parâmetro "dado" | ||
arvore(const T & dado); | arvore(const T & dado); | ||
+ | |||
+ | // cria uma árvore cujos nodos contêm os dados contidos na lista "dados" | ||
+ | arvore(lista<T> & dados); | ||
+ | |||
+ | // cria uma árvore cujos nodos contêm os dados contidos na stream "inp" (que pode ser um arquivo) | ||
+ | arvore(istream & inp); | ||
+ | |||
+ | // cria uma árvore que é uma cópia de "outra" | ||
+ | arvore(const arvore<T> & outra); | ||
+ | |||
+ | // destrutor da árvore | ||
~arvore(); | ~arvore(); | ||
+ | // adiciona um dado à árvore | ||
void adiciona(const T& algo); | void adiciona(const T& algo); | ||
− | const T& obtem(const T & algo); | + | |
+ | // acessa um dado contido na árvore. OBS o dado acessado não pode ser modificado ! | ||
+ | const T& obtem(const T & algo) const; | ||
+ | |||
+ | // obtém o valor da raiz da árvore. OBS esse valor não pode ser modificado ! | ||
+ | const T& obtem() const ; | ||
+ | |||
+ | // operações de enumeração dos dados da árvore | ||
void listeInOrder(lista<T> & result); | void listeInOrder(lista<T> & result); | ||
void listePreOrder(lista<T> & result); | void listePreOrder(lista<T> & result); | ||
void listePostOrder(lista<T> & result); | void listePostOrder(lista<T> & result); | ||
void listeEmLargura(lista<T> & result); | void listeEmLargura(lista<T> & result); | ||
− | unsigned int tamanho() const; | + | |
+ | // retorna a quantidade de dados contidos na árvore | ||
+ | unsigned int tamanho() const; | ||
+ | |||
+ | // retorna a altura da árvore | ||
unsigned int altura() ; | unsigned int altura() ; | ||
+ | |||
+ | // retorna o fator de balanceamento da árvore (em torno da raiz) | ||
int fatorB() ; | int fatorB() ; | ||
+ | |||
+ | // balanceia a árvore usando o algoritmo AVL | ||
+ | // retorna a nova raiz da árvore | ||
arvore<T> * balanceia(); | arvore<T> * balanceia(); | ||
+ | |||
+ | // balanceia a árvore usando o algoritmo AVL | ||
+ | // se o parâmetro "otimo" for true, repete o balanceamento sucessivamente, até que | ||
+ | // a altura da árvore não mais reduza | ||
+ | // retorna a nova raiz da árvore | ||
arvore<T> * balanceia(bool otimo); | arvore<T> * balanceia(bool otimo); | ||
− | + | ||
− | // | + | // retorna a subárvore esquerda |
+ | arvore<T> * esquerda(); | ||
+ | |||
+ | // retorna a subárvore direita | ||
+ | arvore<T> * direita(); | ||
+ | |||
+ | // Iteração da árvore (in-order) | ||
void inicia(); | void inicia(); | ||
bool fim(); | bool fim(); | ||
− | + | T& proximo(); | |
− | + | ||
− | // | + | // iteração reversa da árvore (in-order) |
void iniciaPeloFim(); | void iniciaPeloFim(); | ||
bool inicio(); | bool inicio(); | ||
− | + | T& anterior(); | |
− | // remove um dado | + | // remove um dado da árvore. Retorna uma cópia do dado removido |
T remove(const T & algo); | T remove(const T & algo); | ||
− | // obtém | + | // obtém o menor dado contido na árvore. OBS esse dado não pode ser modificado |
− | + | T & obtemMenor() const; | |
− | + | ||
− | + | // obtém o maior dado contido na árvore. OBS esse dado não pode ser modificado | |
+ | T & obtemMaior() const; | ||
+ | |||
+ | // obtém os dados menores que "algo" | ||
void obtemMenoresQue(lista<T> & result, const T & algo); | void obtemMenoresQue(lista<T> & result, const T & algo); | ||
+ | |||
+ | // obtém os dados maiores que "algo" | ||
void obtemMaioresQue(lista<T> & result, const T & algo); | void obtemMaioresQue(lista<T> & result, const T & algo); | ||
Linha 56: | Linha 108: | ||
protected: | protected: | ||
T data; | T data; | ||
− | arvore<T> * esq, * dir; | + | arvore<T> * esq, * dir, * pai; |
− | |||
arvore<T> * rotacionaL(); | arvore<T> * rotacionaL(); | ||
arvore<T> * rotacionaR(); | arvore<T> * rotacionaR(); |
Edição das 13h21min de 19 de novembro de 2019
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
#include <istream>
#include <string>
using std::string;
using std::istream;
namespace prglib {
template <typename T> class arvore {
public:
// este construtor na prática não deve ser usado ...
arvore();
// cria um nodo da árvore, o qual contém o dado passado no parâmetro "dado"
arvore(const T & dado);
// cria uma árvore cujos nodos contêm os dados contidos na lista "dados"
arvore(lista<T> & dados);
// cria uma árvore cujos nodos contêm os dados contidos na stream "inp" (que pode ser um arquivo)
arvore(istream & inp);
// cria uma árvore que é uma cópia de "outra"
arvore(const arvore<T> & outra);
// destrutor da árvore
~arvore();
// adiciona um dado à árvore
void adiciona(const T& algo);
// acessa um dado contido na árvore. OBS o dado acessado não pode ser modificado !
const T& obtem(const T & algo) const;
// obtém o valor da raiz da árvore. OBS esse valor não pode ser modificado !
const T& obtem() const ;
// operações de enumeração dos dados da árvore
void listeInOrder(lista<T> & result);
void listePreOrder(lista<T> & result);
void listePostOrder(lista<T> & result);
void listeEmLargura(lista<T> & result);
// retorna a quantidade de dados contidos na árvore
unsigned int tamanho() const;
// retorna a altura da árvore
unsigned int altura() ;
// retorna o fator de balanceamento da árvore (em torno da raiz)
int fatorB() ;
// balanceia a árvore usando o algoritmo AVL
// retorna a nova raiz da árvore
arvore<T> * balanceia();
// balanceia a árvore usando o algoritmo AVL
// se o parâmetro "otimo" for true, repete o balanceamento sucessivamente, até que
// a altura da árvore não mais reduza
// retorna a nova raiz da árvore
arvore<T> * balanceia(bool otimo);
// retorna a subárvore esquerda
arvore<T> * esquerda();
// retorna a subárvore direita
arvore<T> * direita();
// Iteração da árvore (in-order)
void inicia();
bool fim();
T& proximo();
// iteração reversa da árvore (in-order)
void iniciaPeloFim();
bool inicio();
T& anterior();
// remove um dado da árvore. Retorna uma cópia do dado removido
T remove(const T & algo);
// obtém o menor dado contido na árvore. OBS esse dado não pode ser modificado
T & obtemMenor() const;
// obtém o maior dado contido na árvore. OBS esse dado não pode ser modificado
T & obtemMaior() const;
// obtém os dados menores que "algo"
void obtemMenoresQue(lista<T> & result, const T & algo);
// obtém os dados maiores que "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, * pai;
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.
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á na introdução sobre árvores binárias. Pela definição, 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 |
|