Mudanças entre as edições de "PRG29003: A implementação da árvore de pesquisa binária"
Linha 399: | Linha 399: | ||
# Implemente a iteração in-order de sua árvore (métodos ''inicia, proximo, fim'') | # 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'') | # Implemente a iteração in-order reversa de sua árvore (métodos ''iniciaPeloFim, anterior, inicio'') | ||
+ | |||
+ | = Balanceamento da árvore = | ||
+ | |||
+ | * [http://en.wikipedia.org/wiki/AVL_tree AVL Tree] | ||
+ | |||
+ | Nos experimentos feitos até agora, as '''árvores de pesquisa binária''' apresentaram um bom desempenho tanto para serem criadas quanto para pesquisarem valores. Foi estudado que isso se deve a uma importante propriedade da árvore binária, que limita à altura da árvore a quantidade de operações de comparação em uma pesquisa qualquer. Como a altura é função do logaritmo da quantidade de nodos, ela tende a crescer muito lentamente com o aumento da quantidade de nodos da árvore (ex: uma árvore com pouco mais 2.3 milhões de nodos teria altura de pelo menos 21). Porém isso depende de os nodos estarem igualmente distribuídos dos dois lados da árvore. Em outras palavras, '''a árvore deve estar balanceada'''. | ||
+ | |||
+ | A partir de hoje iremos estudar como balancear uma árvore binária, e para isso usaremos o algoritmo clássico [http://en.wikipedia.org/wiki/AVL_tree AVL]. Mas outras abordagens existem, tais como [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree árvores vermelho-preto]. Uma [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Applications_and_related_data_structures interessante comparação entre árvores AVL e Vermelho-Preto] pode ser lida na Wikipedia: | ||
+ | |||
+ | <syntaxhighlight lang=text> | ||
+ | Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. | ||
+ | Not only does this make them valuable in time-sensitive applications such as real-time applications, | ||
+ | but it makes them valuable building blocks in other data structures which provide worst-case | ||
+ | guarantees; for example, many data structures used in computational geometry can be based on | ||
+ | red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black | ||
+ | trees. | ||
+ | |||
+ | The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more | ||
+ | rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. | ||
+ | This makes it attractive for data structures that may be built once and loaded without | ||
+ | reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an | ||
+ | assembler or interpreter). | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | == Fator de balanceamento == | ||
+ | |||
+ | O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim: | ||
+ | |||
+ | |||
+ | <math>F_b = altura(esquerda) -altura(direita)</math> | ||
+ | |||
+ | |||
+ | Se para todos os nodos da árvore <math>\lVert F_b \rVert <= 1</math>, então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo <math>\lVert F_b \rVert > 1</math>, então existe um desequilíbrio (má distribuição de nodos), o qual pode ser corrigido. | ||
+ | |||
+ | |||
+ | O balanceamento pode ser feito realizando rotações da árvore. | ||
+ | |||
+ | == Rotações e balanceamento == | ||
+ | |||
+ | O balanceamento da árvore implica equilibrar as alturas de cada árvore esquerda e direita dentro de uma árvore. Essa operação pode ser feita tendo como base o que se chama de ''rotações'' da árvore. Duas rotações básicas são possíveis: rotação à direita e à esquerda. Ambas rotações preservam a propriedade de relação de precedência dos dados contidos na árvore: à esquerda da raiz estão os dados menores que o valor da raiz, e à direita estão os maiores. Na figura a seguir, os círculos representam nodos e os triângulos representam subárvores. | ||
+ | |||
+ | [[imagem:PRG2-Rotacoes.jpg]] | ||
+ | |||
+ | |||
+ | Combinando-se essas duas rotações básicas, podem-se realizar quatro tipo de transformações necessárias para o balanceamento de uma árvore AVL: | ||
+ | |||
+ | [[imagem:LL2.jpg|500px]] | ||
+ | <br>''Caso 1: rotação direita'' | ||
+ | |||
+ | |||
+ | [[imagem:LR2.jpg|500px]] | ||
+ | <br>''Caso 2: rotação esquerda da árvore esquerda'' | ||
+ | |||
+ | |||
+ | [[imagem:RR2.jpg|500px]] | ||
+ | <br>''Caso 3: rotação esquerda'' | ||
+ | |||
+ | |||
+ | [[imagem:RL2.jpg|500px]] | ||
+ | <br>''Caso 4: rotação direita da árvore direita'' | ||
+ | |||
+ | |||
+ | O balanceamento é feito combinando-se as rotações elementares (direita e esquerda) para aplicá-las a cada caso, o que aqui se chama de ''redução''. A cada ''redução'' reduz-se o módulo do fator de balanceamento em uma unidade. Portanto se esse fator tiver um valor elevado, várias ''reduções'' sucessivas serão necessárias até que ele fique dentro do limite aceitável (i.e. <math>\vert F_b \vert <= 1</math>). As ''reduções'' podem ser feitas à direita ou esquerda: | ||
+ | * '''<math>F_b < -1</math>: redução à direita:''' | ||
+ | *# ''Se caso 4:'' executa-se ''rotacionaR'' na árvore direita | ||
+ | *# executa-se ''rotacionaL'' | ||
+ | * '''<math>F_b > 1</math>: redução à esquerda:''' | ||
+ | *# ''Se caso 2:'' executa-se ''rotacionaL'' na árvore esquerda | ||
+ | *# executa-se ''rotacionaR'' | ||
+ | |||
+ | |||
+ | O algoritmo de balanceamento pode ser modelado da seguinte forma: | ||
+ | |||
+ | <syntaxhighlight lang=text> | ||
+ | algoritmo balanceia(arvore): | ||
+ | entrada: arvore (modificada ao final do algoritmo) | ||
+ | valor de retorno: raiz da árvore após balanceamento | ||
+ | variáveis: Fb (inteiro) | ||
+ | |||
+ | se arvore esquerda nao nula entao | ||
+ | arvore esquerda <- balanceia(arvore esquerda) | ||
+ | |||
+ | se arvore direita nao nula entao | ||
+ | arvore direita <- balanceia(arvore direita) | ||
+ | |||
+ | Fb <- calcula fator de balanceamento da arvore | ||
+ | |||
+ | enquanto Fb < -1 faça | ||
+ | reduz à direita e calcula novo Fb | ||
+ | fimEnquanto | ||
+ | |||
+ | enquanto Fb > 1 faça | ||
+ | reduz à esquerda e calcula novo Fb | ||
+ | fimEnquanto | ||
+ | |||
+ | retorna arvore | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | Tanto as rotações quanto o balanceamento devem ser implementados como métodos da ''classe arvore''. As rotações pode ser declaradas como métodos protegidos ou privativos, pois devem ser usados somente pelo algoritmo de balanceamento: | ||
+ | |||
+ | <syntaxhighlight lang=c> | ||
+ | template <class T> class arvore { | ||
+ | protected: | ||
+ | // os atributos de uma arvore | ||
+ | public: | ||
+ | // os métodos públicos da Arvore | ||
+ | |||
+ | // A operação que calcula o fator de balanceamento | ||
+ | int fatorB() const; | ||
+ | |||
+ | // A operação que balanceia a árvore | ||
+ | // note que ela retorna um ponteiro para a nova raiz ... | ||
+ | arvore<T> * balanceia(); | ||
+ | arvore<T> * balanceia(bool otimo); | ||
+ | |||
+ | // os métodos protegidos da Arvore ... por enquanto são públicos | ||
+ | // Quando estiverem prontos, devem ficar protegidos ou privativos | ||
+ | |||
+ | // rotação esquerda: retorna a nova raiz da árvore | ||
+ | arvore<T> * rotacionaL(); | ||
+ | |||
+ | // rotação direita: retorna a nova raiz da árvore | ||
+ | arvore<T> * rotacionaR(); | ||
+ | }; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Assim ... implemente o balanceamento da sua árvore ! Dicas: | ||
+ | # Implemente o fator de balanceamento | ||
+ | # Implemente cada uma das rotações, testando-as em árvores pequenas com diferentes topologias. | ||
+ | # Tendo as rotações corretas, implemente o algoritmo de balanceamento. Teste-o com pequenas árvores cujas topologias sejam conhecidas. Verifique a altura e fator de balanceamento dessas árvores antes e após o balanceamento. | ||
+ | |||
+ | |||
+ | {{collapse top | Método escrevaSe reescrito para ajudar a visualizar a topologia da árvore}} | ||
+ | Acrescente isto ao arquivo ''arvore.h'', antes da declaração da classe arvore: | ||
+ | <syntaxhighlight lang=c> | ||
+ | #include <ostream> | ||
+ | |||
+ | using std::ostream; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Acrescente este método à declaração dos métodos públicos da classe arvore em ''arvore.h'' | ||
+ | <syntaxhighlight lang=c> | ||
+ | void escrevaSe(ostream & out) const; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | |||
+ | Acrescente isto a ''arvore-impl.h'' | ||
+ | <syntaxhighlight lang=c> | ||
+ | #include <string> | ||
+ | |||
+ | using std::string; | ||
+ | |||
+ | template <typename T> void arvore<T>::escrevaSe(ostream& out) const { | ||
+ | static int nivel = -1; | ||
+ | string prefixo; | ||
+ | |||
+ | nivel++; | ||
+ | prefixo.append(nivel, ' '); | ||
+ | |||
+ | if (dir) dir->escrevaSe(out); | ||
+ | out << prefixo << data << std::endl; | ||
+ | if (esq) esq->escrevaSe(out); | ||
+ | nivel--; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | {{collapse bottom}} | ||
+ | {{collapse top | Programa de teste das rotações: testa rotacionaL e rotacionaR}} | ||
+ | <syntaxhighlight lang=c> | ||
+ | #include <iostream> | ||
+ | #include <string> | ||
+ | #include <prglib.h> | ||
+ | |||
+ | using namespace std; | ||
+ | using prglib::arvore; | ||
+ | |||
+ | int main() { | ||
+ | arvore<int> * arv; | ||
+ | |||
+ | // uma árvore toda pro lado direito | ||
+ | arv = new arvore<int>(2); | ||
+ | arv->adiciona(3); | ||
+ | arv->adiciona(4); | ||
+ | arv->adiciona(5); | ||
+ | arv->adiciona(6); | ||
+ | |||
+ | arv->escrevaSe(cout); | ||
+ | cout << endl; | ||
+ | |||
+ | arv = arv->rotacionaL(); | ||
+ | arv->escrevaSe(cout); | ||
+ | cout << endl; | ||
+ | |||
+ | arv = arv->rotacionaR(); | ||
+ | arv->escrevaSe(cout); | ||
+ | cout << endl; | ||
+ | |||
+ | delete arv; | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | {{collapse bottom}} | ||
+ | |||
+ | == Atividade == | ||
+ | |||
+ | # 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). |
Edição das 07h45min 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 |
|