Árvores

Árvore é o grafo mais importante da computação. Sistemas de arquivos, índices de banco, árvores sintáticas, hierarquias de herança, o DOM — todos são árvores. A razão é sua propriedade central: caminho único entre quaisquer dois vértices, o que elimina ambiguidade de navegação.

Definição e caracterizações

Uma árvore é um grafo conexo e acíclico. Para um grafo $G$ com $n$ vértices, as afirmações abaixo são todas equivalentes:

1. $G$ é conexo e acíclico.
2. $G$ é conexo e tem exatamente $n-1$ arestas.
3. $G$ é acíclico e tem exatamente $n-1$ arestas.
4. Existe caminho único entre quaisquer dois vértices.
5. $G$ é conexo, e remover qualquer aresta o desconecta.
6. $G$ é acíclico, e acrescentar qualquer aresta cria um ciclo.

Ter seis caracterizações equivalentes é o que torna árvores tão fáceis de trabalhar: para provar que algo é árvore, escolha a condição mais conveniente.

Um grafo acíclico não necessariamente conexo é uma floresta.

Árvores enraizadas

Escolher um vértice como raiz induz orientação: cada vértice ganha um pai (exceto a raiz) e zero ou mais filhos.

Termo	Significado
Folha	Vértice sem filhos
Nó interno	Vértice com pelo menos um filho
Profundidade	Distância da raiz até o nó
Altura	Maior profundidade da árvore
Ancestral	Qualquer nó no caminho até a raiz

Uma árvore binária de altura $h$ tem no máximo $2^{h+1}-1$ nós, logo uma árvore com $n$ nós tem altura mínima $\lceil \log_2(n+1) \rceil - 1$.

Essa desigualdade é o que fundamenta as estruturas balanceadas: manter a altura em $\Theta(\log n)$ garante busca logarítmica. Uma árvore de busca degenerada — inserções em ordem crescente sem balanceamento — vira uma lista ligada com altura $n$, e a busca cai para $O(n)$.

Percursos

def em_ordem(no):
    if no:
        em_ordem(no.esq)
        visita(no)
        em_ordem(no.dir)

Percurso	Ordem	Uso típico
Pré-ordem	raiz, esquerda, direita	Copiar a árvore, serializar
Em ordem	esquerda, raiz, direita	Listar em ordem crescente numa BST
Pós-ordem	esquerda, direita, raiz	Liberar memória, avaliar expressão
Em largura	por nível	Achar o nó mais raso, imprimir níveis

Numa árvore de expressão, pré-ordem produz notação prefixa (polonesa) e pós-ordem produz notação pós-fixa (polonesa reversa) — que é exatamente o que uma máquina de pilha executa. É por isso que compiladores geram código percorrendo a árvore sintática em pós-ordem.

Árvore geradora mínima

Dado um grafo conexo ponderado, a árvore geradora mínima (AGM) é a árvore que conecta todos os vértices com peso total mínimo.

Kruskal. Ordene as arestas por peso e acrescente cada uma que não forme ciclo, usando union-find para o teste. Custo $O(E \log E)$.

Prim. Cresça a árvore a partir de um vértice, sempre pegando a aresta mais leve que sai do conjunto atual. Com heap de Fibonacci, $O(E + V \log V)$.

Ambos são algoritmos gulosos, e ambos funcionam pela propriedade do corte: para qualquer partição dos vértices em dois conjuntos, a aresta mais leve que cruza a partição pertence a alguma AGM.

Aplicações: projeto de redes com custo mínimo de cabeamento, agrupamento hierárquico (cortar as $k-1$ arestas mais pesadas da AGM dá $k$ grupos) e aproximações para o caixeiro viajante.

Estruturas de dados derivadas

Árvore binária de busca. Invariante: tudo à esquerda é menor, tudo à direita é maior. Busca, inserção e remoção em $O(h)$.

AVL e rubro-negra. Mantêm $h = O(\log n)$ por rotações. AVL é mais rigidamente balanceada (busca ligeiramente mais rápida); rubro-negra faz menos rotações (inserção e remoção mais rápidas). std::map do C++ e TreeMap do Java usam rubro-negra.

Árvore B e B+. Alta aridade para minimizar acessos a disco. Um nó ocupa uma página, e com aridade de algumas centenas a altura fica em 3 ou 4 mesmo com bilhões de chaves. É a estrutura de praticamente todo índice de banco de dados e de vários sistemas de arquivos.

Heap binário. Árvore quase completa com a propriedade de que o pai domina os filhos. Armazenado em vetor, sem ponteiros: os filhos de $i$ são $2i+1$ e $2i+2$. Base de filas de prioridade e do heapsort.

Trie. Árvore indexada por prefixos de cadeia. Busca em $O(m)$ com $m$ o comprimento da chave, independente do número de chaves armazenadas.

Árvore de Merkle. Cada nó guarda o resumo criptográfico dos filhos. Permite verificar a integridade de um item com $O(\log n)$ resumos — a base de Git, blockchains e sistemas de arquivos verificáveis.

Exemplo trabalhado

Uma árvore binária completa de altura $3$ tem quantos nós e quantas folhas?

Nós: $2^{3+1} - 1 = 15$. Folhas: $2^3 = 8$. Nós internos: $15 - 8 = 7$ — confirmando que numa árvore binária completa o número de folhas é o de internos mais um.

Erros comuns

• Não balancear uma árvore de busca e obter $O(n)$ em dados ordenados.
• Confundir altura com profundidade. Altura é da árvore; profundidade é de um nó.
• Recursão profunda estourando a pilha em árvores degeneradas.
• Modificar a chave de um nó já inserido, quebrando o invariante da estrutura.
• Usar árvore onde uma tabela hash serve. Se a ordem não importa, hash é mais rápido.

Leituras recomendadas

• Cormen et al., capítulos 12 e 13 — árvores de busca e rubro-negras, com todas as provas de balanceamento.
• Knuth, TAOCP volume 3 — o tratamento clássico e exaustivo de árvores de busca e ordenação.
• Documentação do PostgreSQL sobre índices B-tree — como a teoria aparece num sistema real de produção.
• Diestel, capítulo 1 — as caracterizações equivalentes de árvore, com provas.

Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein (2009). Introduction to Algorithms. MIT Press. ISBN 9780262533058. Donald E. Knuth (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley. Página oficial. Reinhard Diestel (2017). Graph Theory. Springer. DOI: 10.1007/978-3-662-53622-3.

Referências

1. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction to Algorithms. MIT Press.
2. Donald E. Knuth (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
3. Reinhard Diestel (2017). Graph Theory. Springer.