Árvore Binária é uma estrutura de dados hierárquica na qual cada nó possui, no máximo, dois filhos, chamados de filho esquerdo e filho direito. É um dos alicerces da ciência da computação, usada em bancos de dados, sistemas de arquivos, compiladores e mecanismos de busca. Segundo Knuth (TAOCP, Vol. 1), a árvore binária é a estrutura recursiva mais estudada da computação, presente em praticamente todo sistema moderno.
Como funciona
Uma árvore binária organiza dados em nós conectados por arestas, partindo de um nó raiz. Cada nó guarda um valor e referências para até dois filhos. Quando um nó não tem filhos, é chamado de folha. A profundidade indica a distância até a raiz, e a altura indica o caminho até a folha mais distante. Essa hierarquia permite operações rápidas de busca, inserção e remoção, especialmente em variantes balanceadas.
Tipos
- Árvore Binária Completa: todos os níveis preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita.
- Árvore Binária Perfeita: todos os níveis totalmente preenchidos.
- Árvore Binária de Busca (BST): valores menores à esquerda e maiores à direita.
- AVL: BST auto-balanceada onde a diferença de altura entre subárvores é no máximo 1.
- Red-Black: BST balanceada por cores, usada no kernel Linux e em bibliotecas C++.
- B-Tree: generalização usada em índices do MySQL, PostgreSQL e sistemas de arquivos.
Aplicações
Árvores binárias sustentam índices de bancos de dados (B-Tree e B+Tree), roteamento de pacotes em redes, sistemas de arquivos como NTFS e ext4, compiladores (via Árvore de Sintaxe Abstrata), heaps de prioridade, autocompletar em interfaces de busca e o algoritmo de Huffman para compressão de arquivos. Segundo a documentação oficial do MySQL, todos os índices padrão do InnoDB são implementados como B-Trees, uma variante direta da árvore binária de busca.
Operações e complexidade
Em uma BST balanceada, busca, inserção e remoção têm complexidade média O(log n). Já em uma árvore degenerada (que se comporta como lista ligada), essas operações caem para O(n). Segundo Cormen (CLRS, 3ª ed.), o balanceamento é o fator crítico que separa uma estrutura eficiente de uma estrutura ineficaz. Por isso, variantes como AVL e Red-Black são preferidas em produção.
Por que estudar Árvore Binária
Dominar árvores binárias é pré-requisito para compreender bancos de dados, sistemas operacionais, compiladores e algoritmos de busca. Empresas como Google, Meta e Amazon incluem o tema em processos seletivos técnicos há mais de duas décadas. Além disso, entender árvores binárias facilita o aprendizado de estruturas mais avançadas, como grafos, heaps, tries e árvores B+.
Leia o artigo completo: Árvore Binária: tipos, operações e aplicações práticas em programação
