[404] Árvores Binárias de Busca

Todas as estruturas que construímos até agora foram lineares — sequências onde cada elemento tem um sucessor. Hoje damos um salto conceitual para uma estrutura hierárquica, que se ramifica como uma árvore genealógica: a árvore binária de busca. Aqui, cada nó pode ter até dois filhos, e a organização inteligente desses ramos permite algo notável — buscar um elemento entre milhões descartando metade das possibilidades a cada passo. É uma das estruturas mais elegantes da computação, e a recursão que aprendemos na aula Recursão: Quando uma Função Chama a Si Mesma vai finalmente revelar todo o seu poder, pois árvores são recursivas por natureza.

A anatomia de uma árvore

Uma árvore é feita de nós, mas diferente das listas, cada nó pode apontar para dois outros: um filho à esquerda e um filho à direita. Alguns termos que usaremos: a raiz é o nó do topo (o ponto de entrada da árvore, análogo à cabeça de uma lista); as folhas são os nós sem filhos (as pontas); e cada nó é, ele mesmo, a raiz de uma subárvore. Essa última ideia — que cada nó é a raiz de uma árvore menor — é a semente da natureza recursiva das árvores.

typedef struct No {
    int valor;
    struct No *esquerda; // subárvore à esquerda
    struct No *direita;  // subárvore à direita
} No;

Compare com o nó de lista: em vez de um único ponteiro proximo, temos dois — esquerda e direita. Essa bifurcação é o que permite a estrutura se ramificar em vez de seguir em linha reta. Um nó folha tem ambos os ponteiros em NULL; um nó interno tem um ou os dois apontando para filhos.

A regra de ouro da árvore de busca

O que torna uma árvore binária de busca (BST, Binary Search Tree) especial é uma regra de ordenação rigorosa que vale para todos os nós: para qualquer nó, todos os valores na sua subárvore esquerda são menores que ele, e todos os valores na subárvore direita são maiores. Essa propriedade, mantida em cada nó, é o que dá à árvore seu poder de busca.

Imagine inserir os valores 50, 30, 70, 20, 40. A árvore resultante teria 50 na raiz; 30 à sua esquerda (menor) e 70 à direita (maior); 20 à esquerda de 30, e 40 à direita de 30. Buscar o valor 40 seria assim: comece na raiz (50); 40 é menor, vá à esquerda (30); 40 é maior, vá à direita (40); encontrado. Três comparações, e a cada uma descartamos metade da árvore que restava. Numa árvore equilibrada com um milhão de nós, você encontra qualquer valor em cerca de 20 passos — contra até um milhão numa busca linear. Essa é a mágica que a regra de ordenação viabiliza.

Inserindo com recursão

A inserção numa BST é onde a recursão brilha. Para inserir um valor, comparamos com o nó atual e descemos recursivamente à esquerda ou à direita, até encontrar um lugar vazio (NULL):

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esquerda;
    struct No *direita;
} No;

No *criar_no(int valor) {
    No *novo = malloc(sizeof(No));
    if (novo == NULL) return NULL;
    novo->valor = valor;
    novo->esquerda = NULL;
    novo->direita = NULL;
    return novo;
}

// insere um valor, retornando a raiz da (sub)árvore
No *inserir(No *raiz, int valor) {
    if (raiz == NULL) {          // CASO BASE: lugar vazio encontrado
        return criar_no(valor);  // cria o nó aqui
    }
    if (valor < raiz->valor) {
        raiz->esquerda = inserir(raiz->esquerda, valor); // desce à esquerda
    } else if (valor > raiz->valor) {
        raiz->direita = inserir(raiz->direita, valor);   // desce à direita
    }
    // se valor == raiz->valor, ignoramos (sem duplicatas)
    return raiz;
}

Observe a estrutura recursiva, que reflete diretamente a definição da árvore. O caso base é encontrar um NULL — o lugar vazio onde o novo nó deve nascer. O caso recursivo compara o valor com o nó atual e delega a inserção à subárvore apropriada (esquerda se menor, direita se maior), reatribuindo o resultado. Esse "chamar a si mesma sobre uma subárvore" é o padrão que domina todas as operações de árvore, e é a recursão da aula Recursão: Quando uma Função Chama a Si Mesma aplicada a uma estrutura que a pede naturalmente.

Buscando um valor

A busca segue exatamente a mesma lógica de descida, comparando e escolhendo o lado:

// retorna 1 se o valor está na árvore, 0 caso contrário
int buscar(No *raiz, int valor) {
    if (raiz == NULL) {
        return 0; // chegou a um NULL: não encontrado
    }
    if (valor == raiz->valor) {
        return 1; // encontrado!
    }
    if (valor < raiz->valor) {
        return buscar(raiz->esquerda, valor); // procura à esquerda
    } else {
        return buscar(raiz->direita, valor);  // procura à direita
    }
}

A busca é a materialização daquela "mágica" que descrevemos: a cada nó, uma comparação decide se paramos (encontrado), descemos à esquerda ou descemos à direita — e o lado não escolhido é inteiramente descartado. É a busca binária que vimos no bsearch (aula qsort e bsearch: Ordenando e Buscando com a Biblioteca), agora incorporada à própria estrutura de dados. Numa árvore equilibrada, o número de comparações cresce apenas logaritmicamente com o número de elementos — uma eficiência extraordinária.

Percorrendo a árvore: o percurso em ordem

Como visitar todos os nós de uma árvore? Há várias formas, mas uma é especialmente elegante para BSTs: o percurso em ordem (in-order), que visita a subárvore esquerda, depois o nó atual, depois a subárvore direita. O resultado surpreendente é que os valores saem em ordem crescente:

void em_ordem(No *raiz) {
    if (raiz == NULL) return; // caso base: subárvore vazia
    em_ordem(raiz->esquerda);   // 1. visita tudo à esquerda (menores)
    printf("%d ", raiz->valor); // 2. visita o nó atual
    em_ordem(raiz->direita);    // 3. visita tudo à direita (maiores)
}

A lógica é linda: por causa da regra de ordenação, visitar primeiro toda a subárvore esquerda garante que os menores valores saiam antes; depois o nó atual; depois a subárvore direita (os maiores). Para a árvore com 50, 30, 70, 20, 40, esse percurso imprime 20 30 40 50 70 — perfeitamente ordenado. Essa é uma propriedade notável das BSTs: elas mantêm seus dados implicitamente ordenados, e um percurso in-order os extrai em sequência. É por isso que árvores de busca servem tanto para busca rápida quanto para manter coleções ordenadas.

Uma ressalva honesta: o equilíbrio importa

Preciso ser transparente sobre uma limitação crucial. Toda a eficiência que descrevi — busca em passos logarítmicos — depende de a árvore estar equilibrada, isto é, com os ramos de profundidade parecida. Mas se você inserir valores já ordenados (1, 2, 3, 4, 5...), cada novo valor sempre vai para a direita, e a árvore "degenera" numa estrutura que é, na prática, uma lista encadeada inclinada — perdendo toda a vantagem, com busca voltando a ser linear. Existem árvores auto-balanceadas (como as árvores AVL e rubro-negras) que reorganizam os nós automaticamente para evitar isso, mas sua implementação é bem mais complexa e foge ao escopo desta aula introdutória. Por ora, guarde a lição: a BST simples é poderosa quando os dados chegam em ordem razoavelmente aleatória, mas vulnerável quando chegam ordenados. Conhecer essa fronteira é entender quando a estrutura serve e quando é preciso algo mais sofisticado.

Liberando a árvore

Como sempre, a memória alocada precisa ser devolvida — e aqui a recursão novamente simplifica tudo. Para liberar uma árvore, liberamos primeiro as duas subárvores e só então o nó atual (um percurso pós-ordem):

void liberar(No *raiz) {
    if (raiz == NULL) return;
    liberar(raiz->esquerda); // libera toda a subárvore esquerda
    liberar(raiz->direita);  // libera toda a subárvore direita
    free(raiz);              // por fim, libera o próprio nó
}

A ordem é essencial: liberamos os filhos antes do pai. Se liberássemos o nó atual primeiro, perderíamos o acesso aos ponteiros esquerda e direita (um use-after-free), sem como alcançar as subárvores para liberá-las. Liberar de baixo para cima — folhas primeiro, raiz por último — garante que nunca acessemos um nó já liberado. É a mesma disciplina da lista, adaptada à ramificação da árvore.

O que vem a seguir

Hoje conhecemos a árvore binária de busca: uma estrutura hierárquica cuja regra de ordenação (menores à esquerda, maiores à direita) permite buscas de eficiência logarítmica, com inserção, busca e percurso expressos com elegância recursiva. Vimos também sua vulnerabilidade ao desequilíbrio, e o percurso in-order que extrai os dados ordenados. Na próxima aula, fechamos o estudo das estruturas de dados clássicas com a tabela hash — uma estrutura que alcança busca em tempo praticamente constante (ainda mais rápida que a árvore) através de uma ideia engenhosa: calcular diretamente onde cada dado deve morar.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 6.5, com exemplo de árvore binária
• Algorithms, Robert Sedgewick — capítulo sobre árvores binárias de busca
• Introduction to Algorithms (CLRS) — Cap. 12, Binary Search Trees, e Cap. 13, árvores balanceadas
• Data Structures Using C, Tenenbaum — implementações de árvores em C
• Visualização interativa de BSTs — https://www.cs.usfca.edu/~galles/visualization/BST.html

Exercícios

Exercício 1

Usando as funções inserir e em_ordem do artigo, monte uma árvore inserindo os valores 50, 30, 70, 20, 40, 60, 80, e imprima-a em ordem. Confirme que a saída é crescente.

int main(void) {
    No *raiz = NULL;
    int valores[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) {
        raiz = inserir(raiz, valores[i]);
    }
    em_ordem(raiz); // 20 30 40 50 60 70 80
    printf("\n");
    liberar(raiz);
    return 0;
}

Exercício 2

Escreva uma função recursiva int contar_nos(No *raiz) que conte o número total de nós na árvore. Dica: o total é 1 (o nó atual) mais os nós das duas subárvores.

int contar_nos(No *raiz) {
    if (raiz == NULL) return 0;              // caso base: árvore vazia
    return 1 + contar_nos(raiz->esquerda)    // este nó + esquerda + direita
             + contar_nos(raiz->direita);
}

Exercício 3

Escreva uma função recursiva int altura(No *raiz) que retorne a altura da árvore (o número de níveis do caminho mais longo da raiz até uma folha). Dica: a altura é 1 mais a maior das alturas das duas subárvores; a altura de uma árvore vazia é 0.

int altura(No *raiz) {
    if (raiz == NULL) return 0; // árvore vazia tem altura 0
    int he = altura(raiz->esquerda);
    int hd = altura(raiz->direita);
    return 1 + (he > hd ? he : hd); // 1 + a maior das duas alturas
}

Exercício 4

Insira os valores 1, 2, 3, 4, 5 nessa ordem numa árvore e descreva (ou desenhe) o formato resultante. Por que essa árvore perde a eficiência de uma BST equilibrada? Como o percurso in-order ainda funciona corretamente?

1
\
2
\
    3
     \
      4
       \
        5

Exercício 5

Explique por que a função liberar precisa liberar as subárvores antes de liberar o nó raiz. O que daria errado se free(raiz) viesse primeiro?