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

• POG

Árvores binárias

• Árvores binárias
• Tabela de rotas no Linux

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 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 pequena árvore binária

Um exemplo de árvore é mostrado na figura acima. 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.

Árvore de Pesquisa Binária

• Árvore de pesquisa binária na Wikipedia

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 a lista telefônica invertida ? 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, seja o projeto 4 implementado com lista encadeada e árvore de pesquisa binária. O custo computacional para localizar um telefone em uma lista é $O(n)$, pois, no pior caso, cada telefone procurado pode ser comparado com todos os telefones 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:

• Criação de uma árvore de pesquisa binária com topologia simples
• Ordenar lista com árvore

Feito esse aquecimento:

1. Crie uma árvore de pesquisa binária contendo as palavras deste arquivo.
2. 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 ...