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.

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

Esta introdução, e um resumo do restante da explicação sobre árvores, pode ser vista também neste video.

Um exemplo de árvore de pesquisa binária

Arquivo de projeto CLion com a árvore no Github

A biblioteca STL não oferece uma árvore de pesquisa binária genérica. Na verdade, existem ali algumas estruturas de dados que internamente são implementadas usando algo parecido com uma árvore de pesquisa binária, tais como map e set. Mas elas não possibilitam explorar as operações típicas desse tipo de árvore, justamente o que queremos para fins de estudo.

A biblioteca prglib possui uma árvore de pesquisa binária simplificada, que foi criada para fins didáticos. 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 : private BasicTree{
 public:
  arvore();
  //arvore(const arvore<T> & outra);
  arvore(const T & dado);
  virtual ~arvore();

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

  // obtém um dado da árvore
  const T& obtem(const T & algo) const;

  // obtém o valor da raiz da árvore
  const T& obtem() const ;

  // enumera os dados in-order, pre-order, post-order e breadth-first
  void listeInOrder(list<T> & result);
  void listePreOrder(list<T> & result);
  void listePostOrder(list<T> & result);
  void listeEmLargura(list<T> & result);

  // retorna a quantidade de dados na árvore
  unsigned int tamanho() const;

  // retorna a subárvore esquerda
  arvore<T> * esquerda();

  // retorna a subárvore direita
  arvore<T> * direita();

  // itera a árvore
  void inicia();
  bool fim();
  T& proximo();

  // itera a árvore de forma reversa
  void iniciaPeloFim();
  bool inicio();
  T& anterior();

  // remove um dado
  T remove(const T & algo);

  // retorna o menor dado
  T & obtemMenor() const;

  // retorna o maior dado
  T & obtemMaior() const;

  // copia na lista "result" os dados menores que "algo"
  void obtemMenoresQue(list<T> & result, const T & algo);

  // copia na lista "result" os dados maiores que "algo"
  void obtemMaioresQue(list<T> & result, const T & algo);
  
  // obtém todos valores entre "start" e "end" (inclusive)
  void obtemIntervalo(list<T> & result, const T & start, const T & end);

  // retorna a altura da folha mais distante da raiz
  unsigned int altura() ;

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

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

  // balanceia a árvore repetidamente, até que a altura não mais se reduza
  arvore<T> * balanceia(bool otimo);
};

arvore.h

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

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

using namespace std;

using prglib::arvore;

/*
 * 
 */
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);

    // testando se dado existe na árvore
    int y;

    cout << "Digite um número: ";
    cin >> y;
    try {
      auto & x = a->obtem(y);
      cout << y << " existe !" << endl;
    } catch (...) {
      cout << y << " NÃO existe !" << endl;
    }
        
    // enumerando os dados ... eles devem aparecer em ordem crescente !
    list<int> l;
    a->listeInOrder(l);
    
    cout << "In-order: ";
    for (auto & x: l) {
      cout << x << ", ";
    }
    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

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 ?
Escreva uma função que gere um diagrama de uma árvore. Para isso, sua função deve gerar uma string que represente uma especificação de uma árvore no formato .dot (definido pelo software Graphviz). Essa string pode ser gravada em um arquivo a partir do qual, usando o programa dot, pode-se gerar um arquivo de imagem contendo um desenho da árvore.

O formato dot é bem simples, ao menos para desenhar uma árvore. O exemplo a seguir mostra o diagrama de uma árvore e a especificação dot correspondente:

Diagrama	Especificação
	strict graph { laranja -- cereja laranja -- morango cereja -- banana cereja -- figo morango -- mamao morango -- tangerina }

Para gerar um arquivo de imagem a partir de uma especificação dot, pode-se usar este comando:

dot -Tpng arquivo.dot > arquivo.png

A função a ser criada se chama gera_diagrama_arvore:

// a função deve ser um template, pois deve funcionar com qualquer tipo de árvore
template <typename T> string gera_diagrama_arvore(arvore<T> * raiz) {
  // corpo da função
}

Para implementá-la, será necessário usar ao menos estes métodos da árvore:

  // obtém o valor da raiz da árvore
  const T& obtem() const ;

  // retorna a subárvore esquerda
  arvore<T> * esquerda();

  // retorna a subárvore direita
  arvore<T> * direita();

6. Use a função gera_diagrama_arvore para gerar diagramas de árvores antes e após seus balanceamentos. Visualize esses diagramas e compare-os !

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 = " << (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:

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.

A enumeração dos dados está disponível de duas maneiras:

Operações que copiam os dados para uma lista: esta forma de enumerar os dados é bem direta, bastando passar uma lista como parâmetro:

  void listeInOrder(lista<T> & result);
  void listePreOrder(lista<T> & result);
  void listePostOrder(lista<T> & result);
  void listeEmLargura(lista<T> & result);

Iteradores: a árvore oferece iteradores do tipo in-order e pre-order, ambos em suas versões diretas e reversas. Eles podem ser usados facilmente em laços:

    // iteradores diretos ...
    preorder_iterator preorder_begin();
    preorder_iterator preorder_end() const;
    inorder_iterator inorder_begin();
    inorder_iterator inorder_end() const;
    // iteradores reversos ...
    preorder_riterator preorder_rbegin();
    preorder_riterator preorder_rend() const;
    inorder_riterator inorder_rbegin();
    inorder_riterator inorder_rend() const;

Por exemplo, para acessar os dados em ordem crescente pode-se fazer assim (arv é o ponteiro para a raiz):

  for (auto it = arv->inorder_begin(); it != arv->inorder_end(); it++) {
    cout << "Dado: " << *it << endl;
  }

Um caso especial da iteração é usar um laço de iteração simplificado. Isso resulta em uma iteração in-order (note que é necessário referenciar o ponteiro da raiz da árvore):
```
  for (auto & dado: *arv) {
    cout << "Dado: " << dado << endl;
  }
```

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.

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:

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)

Trie na Wikipedia

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

Árvore B na Wikipedia

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

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

Índice

Árvore de Pesquisa Binária

Um exemplo de árvore de pesquisa binária

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

Atividade

Outras operações da árvore de pesquisa binária

Atividade

Alguns outros tipos de árvores

Árvores de expressão binária

Avaliando uma expressão contida em um árvore de expressão binária

Construção de uma árvore de expressão binária

Radix tree (trie)

Árvores B

Árvores binárias no kernel Linux

Menu de navegação

Pesquisa