PRG29003: Introdução a árvores binárias
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
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 é , 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 , contanto que certas propriedades da árvore sejam verificadas (isso será discutido mais adiante).
A árvore de pesquisa binária da prglib
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);
};
|
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:
Feito esse aquecimento:
- Crie uma árvore de pesquisa binária contendo as palavras deste arquivo.
- Procure cada uma das palavras contidas na árvore. Meça quanto tempo levou para encontrá-las (média, menor e maior valor)
- Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma lista.
- Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma tabela hash.
- Compare os tempos gastos em cada caso ...