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:

$h(A)={\begin{cases}0,{\text{if }}A_{esq}=NULL\land A_{dir}=NULL\\1+max(h(A_{esq}),h(A_{dir})),{\text{caso contrario}}\\\end{cases}}$

PRG29003: A implementação da árvore de pesquisa binária

Índice

Começando uma árvore binária

Atividade

Menu de navegação

Pesquisa