Mudanças entre as edições de "PRG29003: A implementação da árvore de pesquisa binária"
Linha 606: | Linha 606: | ||
# Implemente o balanceamento AVL de sua árvore, e aplique-o à árvore criada a partir das palavras do [http://tele.sj.ifsc.edu.br/~msobral/prg2/portugues.zip arquivo de portugues]. A altura inicial da árvore é 42, e a altura após o balanceamento pode chegar a 21 (experimente realizar alguns balanceamentos sucessivos, até que a altura não mais reduza). | # Implemente o balanceamento AVL de sua árvore, e aplique-o à árvore criada a partir das palavras do [http://tele.sj.ifsc.edu.br/~msobral/prg2/portugues.zip arquivo de portugues]. A altura inicial da árvore é 42, e a altura após o balanceamento pode chegar a 21 (experimente realizar alguns balanceamentos sucessivos, até que a altura não mais reduza). | ||
+ | |||
+ | = Remoção de um dado da árvore = | ||
+ | |||
+ | Apesar de não ter sido necessário no Projeto 4, uma outra aplicação da árvore pode necessitar remover dados. Uma forma de fazer isso é listar todos os dados da árvore, remover os dados desejados e, em seguida, reconstruir a árvore, porém isso envolve um grande esforço computacional desnecessário. A solução mais simples é remover somente os dados desejados, fazendo talvez um ajuste pontual na estrutura da árvore. A operação ''remove'' definida abaixo deve implementar tal algoritmo . | ||
+ | |||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | // Este método da classe Arvore remove um nodo que seja igual a "algo" | ||
+ | // Retorna o dado removido. | ||
+ | // Se o dado não for encontrado, dispara uma exceção | ||
+ | T remove(const T & algo); | ||
+ | </syntaxhighlight> | ||
+ | ''O método para remoção de um nodo da árvore, conforme declarado em arvore.h'' | ||
+ | |||
+ | |||
+ | A remoção de um dado de uma árvore de pesquisa binária tem o seguinte princípio: | ||
+ | # Localiza-se o nodo que contém o dado a ser removido. | ||
+ | # Substitui-se o valor desse nodo por '''uma''' destas alternativas: | ||
+ | #* O '''maior''' valor existente '''à esquerda''' do nodo a ser removido. | ||
+ | #* O '''menor''' valor existente '''à direita''' do nodo a ser removido. | ||
+ | |||
+ | |||
+ | A figura abaixo ilustra a remoção de um dado de uma árvore, destacando as duas possibilidades para a operação: | ||
+ | |||
+ | |||
+ | [[imagem:Prg2-arvores-Remocao.png|600px]] | ||
+ | |||
+ | |||
+ | No exemplo acima, o menor valor à direita do nodo a ser removido é fácil de ser encontrado: basta seguir os ramos à esquerda da subárvore direita. O maior valor à esquerda também é fácil de ser encontrado: basta seguir os ramos à direita da subárvore esquerda. Mas o caso geral pode ficar mais complicado. Por exemplo, seja a árvore abaixo: | ||
+ | |||
+ | |||
+ | [[imagem:Prg2-Remocao2.png|350px]] | ||
+ | |||
+ | |||
+ | Nesse exemplo, o menor valor à direita do nodo a ser removido não é uma folha, nem pode ser encontrado simplesmente seguindo-se os ramos esquerdos da árvore direita. O mesmo vale para o maior valor à esquerda. | ||
+ | |||
+ | |||
+ | Para funcionar em todos os casos, o algoritmo de remoção de um dado da árvore pode ser resumido por este pseudo-código: | ||
+ | |||
+ | <syntaxhighlight lang=text> | ||
+ | Localize o valor a ser removido | ||
+ | |||
+ | Se for uma folha, remove o nodo e retorna | ||
+ | |||
+ | Se fator de balanceamento da árvore enraizada no nodo a ser removido for maior que zero, então | ||
+ | Procura o maior valor da árvore esquerda | ||
+ | Copia esse valor para o nodo que contém o valor a ser removido | ||
+ | Remove esse maior valor da árvore esquerda | ||
+ | Senão | ||
+ | Procura o menor valor da árvore direita | ||
+ | Copia esse valor para o nodo que contém o valor a ser removido | ||
+ | Remove esse menor valor da árvore direita | ||
+ | fimSe | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | Além do método ''remove'', dois outros métodos precisam ser implementados para obter o maior ou o menor valor de uma árvore: | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | // Este método da classe Arvore remove um nodo que seja igual a "algo" | ||
+ | // Retorna o dado que foi removido. Se o dado não for encontrado, dispara uma exceção | ||
+ | // A raiz da árvore pode ser modificada no processo ... | ||
+ | T remove(const T & algo); | ||
+ | |||
+ | // Retorna o menor dado da árvore | ||
+ | T & obtemMenor() const; | ||
+ | |||
+ | // Retorna o mair dado da árvore | ||
+ | T & obtemMaior() const; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | {{collapse top | Programa de teste para remoção de valor da árvore}} | ||
+ | <syntaxhighlight lang=c> | ||
+ | #include <iostream> | ||
+ | #include <string> | ||
+ | #include <prglib.h> | ||
+ | |||
+ | using prglib::arvore; | ||
+ | using namespace std; | ||
+ | |||
+ | int main() { | ||
+ | string dados[7] = {"um", "teste", "pequeno", "muito", "da", "simples", "arvore"}; | ||
+ | |||
+ | auto arv = new arvore<string>(dados[3]); | ||
+ | |||
+ | for (int k=1; k < 4; k++) { | ||
+ | arv->adiciona(dados[k+3]); | ||
+ | arv->adiciona(dados[3-k]); | ||
+ | } | ||
+ | |||
+ | arv->escrevaSe(cout); | ||
+ | |||
+ | string dado = arv->remove(dados[1]); | ||
+ | cout << "Removeu " << dado << endl; | ||
+ | arv->escrevaSe(cout); | ||
+ | |||
+ | dado = arv->remove(dados[3]); | ||
+ | cout << "Removeu raiz: " << dado << endl; | ||
+ | arv->escrevaSe(cout); | ||
+ | |||
+ | delete arv; | ||
+ | |||
+ | return 0; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | {{collapse bottom}} | ||
+ | |||
+ | == Atividade == | ||
+ | |||
+ | # Implemente o método ''remove'', e teste-o com o programa de teste. Experimente remover: | ||
+ | #* um valor de uma folha | ||
+ | #* um valor que esteja em um nodo intermediário | ||
+ | #* o valor que está na raiz |
Edição das 20h07min de 18 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 |
|