Uma estrutura de dados que possibilita consultas rápidas se chama árvore. Tal estrutura mantém os dados organizados de forma hierárquica, o que reduz bastante a quantidade de comparações necessárias para se encontrar algum valor. Um exemplo é a árvore de diretórios, que organiza os arquivos em disco em diretórios que formam um diagrama hierarquizado. Esse tipo de estrutura é largamente utilizada em bancos de dados, e também possui diversas aplicações em muitas outras áreas de conhecimento (redes de computadores, análise combinatória, mapas digitais, sistemas de decisão, linguística, diagramas em geral).

Uma árvore de decisão

Uma árvore real ... e binária !

Um exemplo de árvore é mostrado na figura a seguir. A hierarquia inicia em um nodo chamado de raiz. Os demais nodos são conectados de forma hierárquica, sem haver caminhos fechados. Cada nodo possui ramos que conectam os nodos um nível abaixo na árvore. Nodos que não possuem ramos são chamados de folhas. Uma árvore cujos nodos possuem no máximo dois ramos cada é chamada de árvore binária, sendo a árvore mais simples que se pode criar.

Uma pequena árvore binária

Árvore de Pesquisa Binária

Árvore de pesquisa binária na Wikipedia

Uma nova estrutura de dados chamada árvore de pesquisa binária proporciona uma grande eficiência no tempo de busca de um dado. Ela também tem outras propriedades interessantes, e que são úteis para resolver diversos problemas.

Uma árvore de pesquisa binária é um tipo especial de árvore binária usada para armazenar valores ordenáveis. Nesse tipo de árvore a seguinte propriedade é verificada em todos os seus nodos:

valores anteriores àquele contido em um nodo ficam na árvore conectada ao ramo esquerdo.
valores sucessores àquele contido em um nodo ficam na árvore conectada ao ramo direito.

Dois exemplos de árvores de pesquisa binárias são mostrados abaixo. No exemplo 1 armazenam-se strings na árvore, e no exemplo 2 armazenam-se números. Em ambos os casos a propriedade da árvore de pesquisa binária é verificada. Note que os valores à esquerda de um nodo são sempre antecessores ao valor desse nodo, e do lado direito são sempre sucessores. Com isso, a estrutura da árvore de pesquisa binária implicitamente ordena os valores armazenados, o que é útil para diversas aplicações.

Exemplo 1	Exemplo 2

Mas por que essa estrutura de dados é eficiente para armazenar um conjunto de dados, para fins de busca ? Basicamente porque, ao hierarquizar os valores, é possível facilmente guardá-los de forma ordenada. Se a árvore estiver bem balanceada (isso é, tem a mesma quantidade de nodos a partir de ambos os ramos de cada nodo), cada comparação da busca divide a quantidade de nodos restante pela metade. Assim, a quantidade de comparações até localizar o valor procurado é limitada superiormente pela altura da árvore (a quantidade de ramos entre o nodo raiz e o nodo folha mais distante da raiz).

Para fins de comparação, imagine que um programa armazene uma grande quantidade de dados em uma lista encadeada ou em uma árvore de pesquisa binária. O custo computacional para localizar um dado em uma lista é $O(n)$ , pois, no pior caso, cada dado procurado pode ser comparado com todos os dados existentes na lista. Se for usada uma árvore de pesquisa binária, esse custo pode ser $O(log_{2}n)$ , contanto que certas propriedades da árvore sejam verificadas (isso será discutido mais adiante).

A árvore de pesquisa binária da prglib

Arquivo de projeto do Netbeans

A biblioteca prglib possui uma árvore de pesquisa binária simplificada. Ela foi implementada como uma classe template, para que a árvore possa armazenar qualquer tipo de dado. No entanto, apenas tipos de dados ordenáveis podem ser armazenados (que possuem uma relação de precedência e implementem os operadores == e <). A árvore possui operações para adicionar, procurar e remover dados, para listar os dados em profundidade (in-order, pre-order e post-order) ou largura, para iterar os dados (apenas in-order), e para balanceamento AVL. A declaração dessa árvore está a seguir.

A árvore de pesquisa binária da prglib

template <typename T> class arvore {
 public:
  arvore();
  arvore(const T & dado);
  virtual ~arvore();

  // adiciona um dado à árvore
  void adiciona(const T& algo);

  // busca um dado na árvore
  T& obtem(const T & algo) const;

  // lista os dados da árvore na sequêcias in-order, pre-order, post-order
  // ou em largura
  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 na árvore
  unsigned int tamanho() const;  
  
  // retorna a altura da folha mais profunda
  unsigned int altura() ;

  // retorna o fator de balanceamento
  int fatorB() ;

  // balanceia a árvore
  arvore<T> * balanceia();

  // balanceia a árvore até não poder mais reduzir sua altura
  arvore<T> * balanceia(bool otimo);
  
  // iterador da árvore (in-order)
  void inicia();
  bool fim();
  T& proximo();

  // iterador reverso da árvore (in-order)
  void iniciaPeloFim();
  bool inicio();
  T& anterior();
  
  // remove um dado
  T remove(const T & algo);

  // obtém uma referência ao menor dado
  T & obtemMenor() const;

  // obtém uma referência ao maior dado
  T & obtemMaior() const;
  
  // obtém uma lista com os dados menores ou maiores que algo
  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);
};

arvore.h

Um exemplo de uso de uma pequena árvore binária é este:

#include <iostream>
#include <prglib.h>

using namespace std;

using prglib::arvore;
using prglib::lista;

/*
 * 
 */
int main(int argc, char** argv) {

    arvore<int> * a = new arvore<int>(10);
    
    a->adiciona(5);
    a->adiciona(7);
    a->adiciona(2);
    a->adiciona(13);
    a->adiciona(11);
    a->adiciona(15);
        
    lista<int> l;
    a->listeInOrder(l);
    
    cout << "In-order: ";
    l.escrevaSe(cout, ", ");
    cout << endl;

    return 0;
}

Atividade

Resolva estes exercícios:

Eficiência da árvore de pesquisa binária

A eficiência das árvores de pesquisa binária para armazenar dados de forma que possam ser localizados rapidamente depende de como esses dados ficam distribuídos na árvore. Se a árvore estiver desequilibrada (desbalanceada), a eficiência nas buscas será reduzida. Hoje veremos alguns fatores relacionados ao balanceamento de árvores, e como garantir que uma árvore fique bem equilibrada.

Quão eficiente ficou sua árvore ?

Uma árvore fica mais eficiente se estiver balanceada. Isso significa que, para cada nodo da árvore, as alturas dos ramos esquerdo e direito diferem em no máximo uma unidade. Se uma árvore possuir essa propriedade, sua altura será minimizada e assim as buscas serão mais rápidas. Para entender porque, veja que uma árvore com altura h pode conter uma certa quantidade de nodos:

Altura	Nodos (máximo)	Exemplo
0	1
1	3
2	7
3	15

De forma geral, a quantidade máxima de nodos que cabem em uma árvore binária com altura h é dada por esta recorrência:

$N_{h}=1+2\cdot N_{h-1}$

... sendo que $N_{0}=1$ . A recorrência acima pode ser escrita mais diretamente como:

$N_{h}=2^{h+1}-1$

Usando esta relação, pode-se descobrir qual a menor altura possível para uma árvore que contenha N nodos:

$h=-1+\lceil log_{2}(1+N)\rceil$

Na prática, as árvores que criamos não estão otimizadas. Porém iremos comparar as alturas dessas árvores com a altura mínima possível para ter uma ideia de quão eficientes elas são.

O cálculo da altura de uma árvore A pode ser feito segundo 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}}$

Fator de balanceamento

O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim:

$F_{b}=altura(esquerda)-altura(direita)$

Se para todos os nodos da árvore $\lVert F_{b}<=1\rVert$ , então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo $\lVert F_{b}>1\rVert$ , então existe um desequilíbrio (má distribuição de nodos), o qual pode ser corrigido.

Criação de árvores balanceadas

Para criar uma árvore balanceada, pode-se fazer o seguinte:

Se a árvore for criada a partir de um conjunto de dados já disponível: uma boa técnica é embaralhar os dados e depois criar a árvore. Isso cria uma árvore aceitavelmente balanceada, se bem que não de forma otimizada. Um ajuste pode ser feito no balanceamento usando-se um algoritmo apropriado.
Se os dados forem acrescentados gradualmente à árvore: correções em seu balanceamento devem ser feitas periodicamente usando-se um algoritmo apropriado.

Em ambos os casos, um algoritmo de balanceamento é útil para fazer com que a árvore fique bem equilibrada. Um desses algoritmos é apresentado a seguir.

Atividade

Arquivo de projeto do Netbeans

Crie a árvore que armazena as palavras contidas neste arquivo. Observe que essas palavras estão ordenadas.
Investigue a altura e fator de balanceamento dessa árvore
Procure modificar a ordem em que as palavras são adicionadas à árvore, de forma que sua altura diminua.

Balanceamento

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 árvore disponibilizada na prglib pode ser balanceada usando o algoritmo clássico AVL. Mas outras abordagens existem, tais como árvores vermelho-preto. A abordagem AVL é mais simples de implementar que RBT, porém a segunda funciona melhor para árvores que são frequentemente modificadas. Uma interessante comparação entre árvores AVL e Vermelho-Preto pode ser lida na Wikipedia:

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).

No caso da árvore da prglib, o balanceamento pode ser realizado por meio do método balanceia:

  // balanceia a arvore usando o algoritmo AVL. 
  // Retorna a raiz da nova arvore ... pois o algoritmo pode modificar a raiz.
  arvore<T> * balanceia();

  // Balanceia o melhor possivel a arvore. Executa o método ''balanceia()'' repetidas
  // vezes, até que a altura da árvore não mais reduza.
  arvore<T> * balanceia(bool otimo);

Um exemplo de como utilizá-lo é mostrado a seguir:

int main() {
  arvore<int> * arv = new arvore<int>(5);

  arv->adiciona(4);
  arv->adiciona(3);
  arv->adiciona(2);
  arv->adiciona(1);
  arv->adiciona(0);

  // a arvore "arv" está totalmente desbalanceada, tendo todos os nodos do lado esquerdo
  // Mostra seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // balanceia a arvore
  arv = arv->balanceia();

  // Mostra novamente seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // destroi a arvore
  delete arv;
}

Atividade

Crie a árvore que armazena as palavras contidas neste arquivo.
Investigue a altura e fator de balanceamento dessa árvore
Balanceie sua árvore, e verifique o novo fator de balanceamento e altura. Compare-os com a menor altura possível teoricamente.
E se a árvore fosse criada aos poucos ? Como ela poderia ser mantida balanceada ?

Feito esse aquecimento:

Crie uma árvore de pesquisa binária contendo as palavras deste arquivo.
Após criar uma árvore balanceada, procure cada uma das palavras contidas na árvore. Meça quanto tempo levou para encontrá-las (média, menor e maior valor)
1. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma lista.
2. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma tabela hash.
3. Compare os tempos gastos em cada caso ...

Como medir tempo decorrido

Use a função clock, que retorna um número correspondente ao valor do relógio do computador (OBS: precisa de #include <time.h>).

    clock_t c1 = clock();
    
    cout << "Testando clock ..." << endl;
    cout.flush();
    
    clock_t c2 = clock();
    
    // calcula o tempo decorrido
    double dt = c2 - c1;
    cout << dt << "ticks = " << dt/CLOCKS_PER_SEC << " s" << endl;

Enumeração dos 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
Pre order	visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore
Post order	visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz
Level order	visitam-se nodos cada nível por vez, da esquerda pra direita

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 usar métodos 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);

Os métodos de enumeração na classe arvore

Ativiodade

Resolva estes exercícios:

PRG29003: Introdução a árvores binárias

Índice

Árvore de Pesquisa Binária

A árvore de pesquisa binária da prglib

Atividade

Eficiência da árvore de pesquisa binária

Quão eficiente ficou sua árvore ?

Fator de balanceamento

Criação de árvores balanceadas

Atividade

Balanceamento

Atividade

Enumeração dos dados de uma árvore

Ativiodade

Menu de navegação

Pesquisa