Árvore binária: no máximo dois filhos

Uma regra que muda tudo

Na árvore genérica da aula anterior, um pai podia ter quantos filhos quisesse: uma pasta com dez subpastas, um chefe com vinte pessoas na equipe. A árvore binária faz um corte: nenhum nó pode ter mais de dois filhos. Só isso. Cada nó tem, no máximo, um filho à esquerda e um filho à direita. Pode ter os dois, pode ter só um dos lados, pode não ter nenhum (aí é folha). O que não pode é ter um terceiro. Essa limitação parece um empobrecimento, mas é o contrário: ao amarrar a forma da árvore, ela permite algoritmos previsíveis e muito mais rápidos, como você verá com a árvore de busca binária.

A posição dos filhos ganha importância na árvore binária. Na árvore comum, os filhos de um nó formam um grupo sem ordem particular. Na binária, existe um lado esquerdo e um lado direito bem definidos, e essa distinção carrega significado. Um nó com um único filho ainda precisa dizer se esse filho está à esquerda ou à direita, porque as duas situações são diferentes. Guarde essa ideia de lado com significado: ela é a chave da próxima aula, em que a esquerda passa a guardar os menores e a direita os maiores.

O nó binário por dentro

Por dentro, um nó de árvore binária é simples: guarda um valor e duas ligações, uma para o filho esquerdo e outra para o direito. Quando um lado não existe, a ligação fica vazia (nula). É o mesmo espírito da lista ligada, em que o nó guardava um valor e uma ligação para o próximo; aqui são duas ligações, o que permite a ramificação. Montar a árvore é criar nós e conectá-los pelas ligações esquerda e direita, do mesmo modo que se religava ponteiros na lista, só que agora com dois caminhos por nó.

no <- { valor: 8, esquerdo: nulo, direito: nulo }
// dar um filho esquerdo e um direito ao nó:
no.esquerdo <- { valor: 3, esquerdo: nulo, direito: nulo }
no.direito  <- { valor: 10, esquerdo: nulo, direito: nulo }
// agora o nó 8 tem 3 à esquerda e 10 à direita
escreva(no.esquerdo.valor)   // mostra 3
escreva(no.direito.valor)    // mostra 10

Cada nó guarda um valor e duas ligações. Vazio é nulo; conectar filhos é preencher a ligação esquerda ou direita.

raiz <- { valor: 5, esquerdo: nulo, direito: nulo }
raiz.esquerdo <- { valor: 2, esquerdo: nulo, direito: nulo }
raiz.direito  <- { valor: 9, esquerdo: nulo, direito: nulo }
raiz.direito.esquerdo <- { valor: 7, esquerdo: nulo, direito: nulo }
escreva(raiz.direito.esquerdo.valor)

Por que dois é o número mágico

Por que justamente dois filhos, e não três ou quatro? Porque dois lados casam perfeitamente com uma decisão do tipo sim ou não, maior ou menor, esquerda ou direita. Boa parte dos problemas de busca se resume a perguntas binárias: o que procuro é menor ou maior que este nó? Com dois filhos, cada nó representa uma dessas perguntas, e cada descida na árvore responde a ela e corta o problema pela metade. É o mesmo princípio da busca binária numa lista ordenada, agora gravado na própria forma da estrutura. Árvores com mais filhos por nó existem e têm seus usos, mas a binária é a base, justamente por espelhar a decisão de dois caminhos.