Nesta aula, mergulhamos no estudo das Árvores Binárias, uma das estruturas de dados mais fundamentais e versáteis da ciência da computação. Exploramos sua definição formal, propriedades matemáticas, tipos especiais, algoritmos clássicos de percurso e uma implementação básica em Python. O objetivo é construir uma base sólida para tópicos mais avançados como Árvores de Busca, AVL, Rubro-Negras e aplicações em compressão e indexação.
O que é uma Árvore Binária?
Uma árvore binária é uma estrutura de dados hierárquica composta por nós, onde cada nó possui no máximo dois filhos, denominados filho esquerdo e filho direito. Os principais componentes são:
- Raiz (Root): O nó no topo da hierarquia, ponto de partida para todos os percursos.
- Nós internos (Internal Nodes): Nós que possuem pelo menos um filho.
- Folhas (Leaves): Nós que não possuem nenhum filho, localizados na base da árvore.
- Arestas (Edges): As conexões entre um nó e seus filhos.
- Altura (Height): O número de arestas no maior caminho da raiz até uma folha.
- Profundidade (Depth): O número de arestas da raiz até um nó específico.
Uma árvore binária vazia (null) é representada pela ausência de nó. Esta definição recursiva é a base para todos os algoritmos que operam sobre árvores binárias, onde cada subárvore (esquerda e direita) é ela mesma uma árvore binária.
Tipos de Árvores Binárias
Existem variações importantes da estrutura básica, cada uma com propriedades específicas que as tornam adequadas para diferentes aplicações:
- Árvore Binária Cheia (Full Binary Tree): Todo nó tem exatamente 0 ou 2 filhos. Não existem nós com apenas um filho.
- Árvore Binária Completa (Complete Binary Tree): Todos os níveis são completamente preenchidos, exceto possivelmente o último nível, que deve ser preenchido da esquerda para a direita. Esta é a base para a implementação de Heaps (montes).
- Árvore Binária Perfeita (Perfect Binary Tree): Todos os nós internos possuem dois filhos e todas as folhas estão no mesmo nível. Uma árvore perfeita de altura h possui 2^(h+1) - 1 nós.
- Árvore Degenerada (Degenerate Tree): Cada nó possui apenas um filho, funcionando na prática como uma lista ligada. O desempenho das operações nela se degrada para O(n).
Percursos em Árvores Binárias
Percorrer uma árvore binária significa visitar todos os seus nós em uma ordem específica. Os três percursos clássicos, definidos recursivamente, são:
| Percurso | Sequência | Uso Comum |
|---|---|---|
| Pré-ordem (Pre-order) | Raiz → Esquerda → Direita | Copiar a estrutura da árvore |
| Em ordem (In-order) | Esquerda → Raiz → Direita | Recuperar elementos em ordem crescente (BST) |
| Pós-ordem (Post-order) | Esquerda → Direita → Raiz | Deletar ou liberar a memória da árvore |
Além destes, o percurso em nível (Level-order ou BFS) visita os nós por profundidade, utilizando uma fila auxiliar. Cada percurso tem complexidade O(n) e é amplamente utilizado em algoritmos de processamento de árvores.
Implementação Básica em Python
Abaixo, uma implementação minimalista de uma Árvore Binária de Busca (BST) em Python, com inserção e percurso em ordem:
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def insert(root, key):
if root is None:
return Node(key)
if key < root.val:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
# Exemplo de uso
if __name__ == "__main__":
root = Node(10)
insert(root, 5)
insert(root, 15)
insert(root, 3)
insert(root, 7)
inorder(root) # Saída: 3 5 7 10 15>A função insert aproveita a propriedade fundamental de uma BST: o nó filho esquerdo é sempre menor que a raiz, e o filho direito é sempre maior. O percurso em ordem, portanto, imprime os elementos de forma ordenada.
Aplicações Práticas
As árvores binárias são onipresentes na computação. Algumas aplicações clássicas incluem:
- Árvores de Busca Binária (BST): Estruturas de dados fundamentais para buscas, inserções e remoções com complexidade média O(log n).
- Montes Binários (Heaps): Utilizados na implementação de filas de prioridade e no algoritmo de ordenação Heapsort.
- Árvores de Expressão: Representação interna de expressões matemáticas em compiladores e calculadoras.
- Codificação de Huffman: Algoritmo de compressão de dados que utiliza uma árvore binária para gerar códigos de tamanho variável.
- Árvores Balanceadas (AVL, Rubro-Negra): Variações que garantem complexidade O(log n) no pior caso para operações de busca.
FAQ / Pontos Principais
O que diferencia uma árvore binária de uma árvore comum?
Em uma árvore binária, cada nó pode ter no máximo dois filhos (esquerdo e direito). Em uma árvore genérica (n-ária), um nó pode ter qualquer número de filhos.
Qual a altura máxima de uma árvore binária com n nós?
No pior caso (árvore degenerada), a altura é n - 1. No melhor caso (árvore perfeita), a altura é log2(n).
O que é uma Árvore Binária de Busca (BST)?
É uma árvore binária onde, para cada nó, todos os valores na subárvore esquerda são menores que o valor do nó, e todos os valores na subárvore direita são maiores. Esta propriedade permite buscas binárias eficientes na estrutura.
Como escolher o tipo de percurso adequado?
A escolha depende da aplicação. Use pré-ordem se precisar processar a raiz antes dos filhos (ex: copiar). Use em ordem se quiser uma sequência ordenada (em BST). Use pós-ordem se precisar processar os filhos antes da raiz (ex: cálculo de altura, deletar nós).