Árvores binárias de busca: estrutura, inserção e percurso explicados

Árvores são uma das estruturas de dados mais versáteis e fundamentais da ciência da computação. De sistemas de arquivos a bancos de dados, de compiladores a sistemas de decisão com IA, árvores aparecem em todo lugar. A Árvore Binária de Busca (BST — Binary Search Tree) é o ponto de entrada para entender árvores: uma estrutura hierárquica com propriedade de ordenação que permite busca, inserção e remoção eficientes em O(log n) para árvores balanceadas. Dominar BSTs é pré-requisito para estruturas mais avançadas como árvores AVL, Red-Black Trees e B-Trees usadas em bancos de dados.

Propriedade da BST

Em uma BST, cada nó tem no máximo dois filhos (esquerdo e direito). A propriedade fundamental: para todo nó N, todos os valores na subárvore esquerda são menores que N, e todos os valores na subárvore direita são maiores que N. Essa propriedade torna a busca eficiente: a cada comparação, metade da árvore é eliminada.

Implementação em Python

class No:
    def __init__(self, valor):
        self.valor = valor
        self.esquerdo = None
        self.direito = None

class ArvoreBinariaBusca:
    def __init__(self):
        self.raiz = None

    def inserir(self, valor):
        self.raiz = self._inserir(self.raiz, valor)

    def _inserir(self, no, valor):
        if no is None:
            return No(valor)
        if valor  no.valor:
            no.direito = self._inserir(no.direito, valor)
        # Se igual, não insere duplicata
        return no

    def buscar(self, valor):
        return self._buscar(self.raiz, valor)

    def _buscar(self, no, valor):
        if no is None:
            return False
        if valor == no.valor:
            return True
        elif valor < no.valor:
            return self._buscar(no.esquerdo, valor)
        else:
            return self._buscar(no.direito, valor)

bst = ArvoreBinariaBusca()
for v in [50, 30, 70, 20, 40, 60, 80]:
    bst.inserir(v)

print(bst.buscar(40))  # True
print(bst.buscar(55))  # False

Percursos em árvores: in-order, pre-order e post-order

Diferentes formas de visitar todos os nós da árvore têm diferentes utilidades:

def in_order(no):
    """Esquerda → Raiz → Direita — visita os nós em ordem crescente na BST"""
    if no:
        in_order(no.esquerdo)
        print(no.valor, end=" ")
        in_order(no.direito)

def pre_order(no):
    """Raiz → Esquerda → Direita — útil para copiar/serializar a árvore"""
    if no:
        print(no.valor, end=" ")
        pre_order(no.esquerdo)
        pre_order(no.direito)

def post_order(no):
    """Esquerda → Direita → Raiz — útil para deletar a árvore (filhos antes do pai)"""
    if no:
        post_order(no.esquerdo)
        post_order(no.direito)
        print(no.valor, end=" ")

in_order(bst.raiz)    # 20 30 40 50 60 70 80 — ordenado!
pre_order(bst.raiz)   # 50 30 20 40 70 60 80
post_order(bst.raiz)  # 20 40 30 60 80 70 50

O problema da BST desbalanceada

A BST tem um problema crítico: se os valores são inseridos em ordem crescente ou decrescente, a árvore degenera numa lista ligada — altura O(n) em vez de O(log n), e busca volta a ser O(n). Por isso existem árvores auto-balanceadas: AVL Trees (primeira árvore auto-balanceada, 1962) e Red-Black Trees (usadas no Java TreeMap, C++ std::map, e nos índices do Linux). Bancos de dados relacionais usam B-Trees e suas variantes, otimizadas para operar em disco em vez de RAM. Para uso em produção, use as implementações nativas (SortedList no Python com bisect, TreeMap no Java) — entender BSTs é base para essas estruturas mais sofisticadas.