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. A quantidade de ramos de um nodo é denominada grau do nodo, e o grau da árvore é dado pelo maior grau dentre os nodos dessa árvore. Nodos com grau zero (que não possuem ramos) são chamados de folhas. Uma árvore com grau dois (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
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
const T& obtem(const T & algo) const;
// obtém o dado que está na raiz desta árvore
const T& obtem() const;
// obtém a subárvore esquerda
arvore<T> * esquerda();
// obtém a subárvore direita
arvore<T> * direita();
// 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:
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:
... sendo que . A recorrência acima pode ser escrita mais diretamente como:
Usando esta relação, pode-se descobrir qual a menor altura possível para uma árvore que contenha N nodos:
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:
Fator de balanceamento
O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim:
Se para todos os nodos da árvore , então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo , 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
- 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
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)
- 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 ...
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 = " << (float)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:
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
Atividade
Resolva estes exercícios:
Outras operações da árvore de pesquisa binária
Outras operações estão disponíveis na árvore de pesquisa binária da prglib. Abaixo segue um resumo dos tipos de operações e respectivos métodos da classe arvore.
- Iteração direta e reversa:
// iterador da árvore (in-order) void inicia(); bool fim(); T& proximo(); // iterador reverso da árvore (in-order) void iniciaPeloFim(); bool inicio(); T& anterior();
- Remoção de um dado:
// remove um dado T remove(const T & algo);
- Busca pelo menor ou maior valor contido na árvore:
// 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);
- Busca de dados dentro de um intervalo:
// obtém todos valores entre "start" e "end" (inclusive) void obtemIntervalo(lista<T> & result, const T & start, const T & end);
- Acesso ao dado da raiz:
// obtém uma referência ao dado contido na raiz const T& obtem() const ;
- Acesso às subárvores esquerda e direita:
// obtém a raiz da subárvore esquerda (nullptr caso não exista) arvore<T> * esquerda(); // obtém a raiz da subárvore direita (nullptr caso não exista) arvore<T> * direita();
Atividade
Resolva estes exercícios:
- Busca de uma faixa de valores (não pode usar obtemIntervalo !)
- Busca palavras por sufixo
- Refaça este exercício sem usar iteração da árvore
Alguns outros tipos de árvores
Árvores de expressão binária
Árvores binárias podem ter outras aplicações além de armazenar dados de forma a possibilitar buscas eficientes. A representação de expressões aritméticas e algébricas é outro uso de árvores. Essas expressões também possuem uma hierarquia, dada pela precedência de operadores, o que as torna passíveis de serem representadas por árvores. Uma vez transformada em uma árvore binária, uma expressão pode ser facilmente avaliada, obtendo-se seu resultado. Esse tipo de árvore é chamado de árvore de expressão binária.
Uma árvore de expressão binária para a expressão (a+b)*c+7
Note-se que ness tipo de árvore as folhas são operandos (constantes ou variáveis), e demais nodos são operadores aritméticos. A topologia da árvore deve respeitar a precedência dos operadores, para que o resultado da expressão possa ser obtido (isso se faz ao percorrê-la segundo in-order).
Árvores de expressão binária são úteis para resolver expressões fornecidas em tempo de execução. Por exemplo, uma calculadora pode permitir que o usuário digite uma expressão a ser calculada, que é lida portanto como uma string. Para resolvê-la, pode-se transformá-la em uma árvore binária, e então calculá-la. Assim, qualquer programa que precise resolver expressões fornecidas pelo usuário pode usar essa técnica para avaliá-las.
Avaliando uma expressão contida em um árvore de expressão binária
Uma árvore de expressão binária devidamente construída pode ser facilmente avaliada se for percorrida in-order. O algoritmo basicamente funciona assim:
algoritmo resolveExpressao(arvore):
Entrada: uma arvore de expressão binária
Saída: o resultado da expressão após sua avaliação
Variáveis locais: operador (tipo caractere), resultado (tipo ponto flutuante)
se arvore for vazia: retorne 0
se arvore for folha: retorne valor da folha
operador = raiz da arvore
Escolha (operador):
caso '+':
resultado = resolveExpressao(arvore esquerda) + resolveExpressao(arvore direita)
caso '-':
resultado = resolveExpressao(arvore esquerda) - resolveExpressao(arvore direita)
caso '*':
resultado = resolveExpressao(arvore esquerda) * resolveExpressao(arvore direita)
caso '/':
resultado = resolveExpressao(arvore esquerda) / resolveExpressao(arvore direita)
caso '%':
resultado = resolveExpressao(arvore esquerda) % resolveExpressao(arvore direita)
caso '^':
resultado = resolveExpressao(arvore esquerda) ^ resolveExpressao(arvore direita)
fim Escolha
retorne resultado
fim resolveExpressao
Construção de uma árvore de expressão binária
A construção automática da árvore inicia com um vetor ou lista composta por um nodo raiz para cada token da expressão. Em seguida, agrupam-se sistematicamente os nodos em árvores cujas raízes sejam operadores. Isso deve ser feito respeitando a precedência dos operadores. O funcionamento desse algoritmo pode ser visualizado pela seguinte sequência de diagramas, que mostra o agrupamento dos nodos de acordo com a precedência de operadores, até que no final haja somente uma árvore:
... e então ? Será que é fácil escrever tal algoritmo ?
Radix tree (trie)
Um trie, ou radix tree, é um tipo de árvore em que as chaves não estão nos nodos e sim nas transições. A chave associada a cada nodo depende da posição do nodo em relação à raiz, tomando-se as transições necessárias para chegar a tal nodo. Valores podem estar associados a folhas e nodos de interesse. Esse tipo de árvore, que NÃO NECESSARIAMENTE É BINÁRIA, é útil para representar conjuntos de dados que podem ser pesquisados por seus prefixos. Exemplos de aplicações são tabelas de roteamento em roteadores e armazenamento de palavras de dicionário (em particular quando se desejam sugerir palavras a partir de suas letras iniciais).
A figura a seguir exemplifica um trie.
Exemplo de trie (obtido na Wikipedia)
Árvores B
Árvores B têm grau arbitrário, e em seus nodos múltiplos dados podem ser armazenados. Se o grau de um nodo dessa árvore for N, a ordem desse nodo (quantidade de dados nele contidos) é N-1. Esse tipo de árvore costuma ser usada para indexar dados em mídia secundária (ex: discos), pois reduz a quantidade de acessos necessários para obter os dados. Além disso, árvores B são auto-balanceadas e possibilitam pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico (ver verbete na Wikipedia).
Exemplo de árvore B (Fonte)
Árvores binárias no kernel Linux
- Estruturas de dados disponíveis dentro do kernel Linux (cap. 6 do livro Linux Kernel Development, 3rd ed., de Robert Love, 2010)
Algumas estruturas de dados estão disponíveis para uso dentro do kernel Linux. Há filas, listas, tabelas hash e árvores binárias para ajudar no desenvolvimento tanto do kernel quanto de módulos e device drivers. Elas não se destinam ao desenvolvedor de aplicações, e sim a desenvolvedores do kernel (esperem a disciplina de SOP para entender melhor isso).
Com respeito a árvores binárias, destaca-se este parágrafo ao final do capítulo do livro:
If you need to store a large amount of data and look it up efficiently, consider a red-
black tree. Red-black trees enable the searching in logarithmic time, while still providing
an efficient linear time in-order traversal.Although more complicated to implement than
the other data structures, their in-memory footprint isn’t significantly worse. If you are
not performing many time-critical look-up operations, a red-black tree probably isn’t
your best bet. In that case, favor a linked list.