O que são árvores binárias

Árvores binárias são estruturas de dados usadas para organizar um conjunto de informações de forma eficiente na memória do computador. Assim como as listas encadeadas e duplamente encadeadas, árvores binárias podem conter grandes quantidades de elementos, mesmo em computadores cuja memória esteja fragmentada (sem espaço para alocar uma matriz, por exemplo).

Também são bastante similares às listas duplamente encadeadas em sua estrutura básica. Todo nó de uma árvore binária contém, ao menos, um item chave (que poderá ser um int, char, char *, etc) e dois outros ponteiros: um para a subárvore esquerda e outro para a subárvore direita. Árvores binárias têm a seguinte estrutura:

struct no {
	int		info;
	struct no	*esquerda;
	struct no	*direita;
};

Porque usar árvores binárias?

• Custos :: Assim como as listas encadeadas, as árvores binárias precisam de relativamente pouco espaço a mais em uma estrutura, para que sua implementação seja possível. É um pequeno custo a se pagar por um benefício gigantesco. Logo, o custo/benefício é excelente.
• Implementação :: É complicado entender perfeitamente o conceito por trás das árvores binárias a primeiro momento, mas depois de um tempo, sua natureza recursiva torna as rotinas de operação extremamente simples. Como veremos mais à frente, os códigos para inserir e procurar são bem simples, deixando quase toda a complexidade para o código de remoção.
• Performance :: Listas duplamente encadeadas têm tempos de inserção, pesquisa e remoção bem ruins. No pior caso, em uma lista com 'n' elementos, você precisará analisar todos os 'n' elementos da lista. Imagine uma lista com 100 milhões de registros? (Como uma lista de emails ou a lista de cidades no mundo inteiro em uma tabela de banco de dados). Demoraria muito! Já as árvores binárias têm uma propriedade interessante: os tempos de inserção, remoção e procura, são, no pior caso "lg(n + 1)" (isto é, log de 'n' na base 2). Para os que não se lembram dos logaritmos, aqui vai uma pequena fórmula:

Isso significa que uma árvore binária (balanceada) possibilitará um tempo de pesquisa fenomenal no pior caso. Em 100 milhões de elementos, as rotinas farão no máximo 27 comparações!

• lg (100.000.001) ~= 27
• 2^27 = 134.217.728

Tipos de árvores binárias

Árvores binárias possuem diversas classificações e é importante saber sobre algumas, para entender o algoritmo implementado. No nosso caso, vamos implementar uma árvore binária de busca simples. Isso quer dizer que ela não se balanceia automaticamente e que pode ser degenerada em uma lista encadeada.

Os algoritmos que tornam e mantêm as árvores binárias em sua plena eficiência, são também os mais complexos. Um destes algoritmos se chama AVL (abreviação do nome de seus criadores) e o outro chama-se Rubro-Negro (Red-Black Trees). Existem outros algoritmos igualmente complexos (ou mais) e também existem outros tipos de implementações de árvores que tiram vantagem até das linhas de cache do processador, aumentando ainda mais a performance da estrutura!

O objetivo principal de todos estes algoritmos é sempre manter a árvore balanceada e maximizar a performance, para que as funções de inserção, remoção e procura, sempre sejam " O(lg(n))" e para que as árvores não se degenerem em listas encadeadas. O AVL mantém a árvore binária balanceada de acordo com a diferença entre as alturas de duas subárvores, já o RedBlack dá "cores" às raízes e realiza balanceamentos de acordo com essas cores.
Este artigo mostra como são implementadas as árvores binárias da maneira mais simples possível, o que significa que elas podem se degenerar em listas encadeadas caso os itens sejam inseridos de forma sequencial. Como dito, os algoritmos para implementar árvores binárias de busca balanceadas são mais complexos, longos e é um ótimo tema para um futuro artigo.

Nomenclatura

Árvores binárias têm sua própria nomenclatura e representação.

• Uma árvore tem uma raiz e essa raiz possui nós (ou filhos, se preferir).
• Imagine a raiz como "virada para o céu" (árvore de cabeça para baixo).
• A árvore cresce para "baixo".
• Quando percorremos a árvore nos distanciando da raiz, estamos subindo a árvore.
• Quando percorremos a árvore em direção à raiz, estamos descendo a árvore.
• Nós, que não possuem nenhuma subárvore, são chamados de folhas.

Neste artigo, chamarei a estrutura base da árvore de Folha - por motivos de simplicidade (e, principalmente, porque não gosto de escrever "noh"). Mas, tudo isso é apenas questão de nomenclatura. Você não precisa saber disso para entender como as árvores funcionam, mas é sempre bom saber.

Também vale dizer que o termo certo para o ato de percorrer cada nó de uma árvore é Transversalização da árvore, mas por motivos de simplicidade, vou sempre dizer percorrer a árvore ou percorrer os nós. É necessário saber que existem três tipos diferentes de transversalização, são eles: ordenado, pré-ordenado e pós-ordenado.

Tomando como exemplo a árvore ilustrada no início dessa introdução, as transversalizações nela, seriam:

• ordenado : 1 2 3 4 5 6 7
• pré-ordenado: 4 2 1 3 6 5 7
• pós-ordenado: 1 3 2 5 7 6 4

Boa leitura!