Árvore de busca binária: menores à esquerda, maiores à direita

A regra que coloca ordem na árvore

A árvore binária, sozinha, é só uma forma. A árvore de busca binária acrescenta uma regra que a torna poderosa: em cada nó, tudo o que for menor que ele fica na subárvore da esquerda, e tudo o que for maior fica na da direita. Essa regra vale para todo nó, não só para a raiz. Com ela, a árvore fica ordenada de um jeito especial: não numa fila reta, mas espalhada de forma que a posição de cada valor conta uma história sobre seu tamanho relativo. Um número lá no fundo à esquerda é dos menores; um lá no fundo à direita é dos maiores. É essa organização silenciosa que faz a busca voar.

Vamos montar uma BST pequena para acompanhar. Comece com a raiz 8. Chega o 3: como 3 é menor que 8, vai para a esquerda. Chega o 10: maior que 8, vai para a direita. Chega o 1: menor que 8 (vai à esquerda), depois menor que 3 (vai à esquerda de novo), e vira folha. Chega o 6: menor que 8 (esquerda), maior que 3 (direita), e vira folha. No fim, a raiz 8 tem o 3 à esquerda e o 10 à direita; o 3 tem o 1 à esquerda e o 6 à direita. Repare que cada inserção foi uma sequência de comparações, sempre descendo para um lado só. Essa mesma árvore vai reaparecer no jogo desta aula.

Buscar descendo uma pergunta por vez

Achar um valor na BST é uma conversa curta com a árvore. Comece na raiz e faça uma pergunta: o valor que procuro é igual, menor ou maior que este nó? Se for igual, achou. Se for menor, o valor só pode estar à esquerda, então desça para o filho esquerdo e ignore todo o lado direito. Se for maior, desça para a direita e ignore o esquerdo. Repita no novo nó. Cada passo descarta um ramo inteiro da árvore, e é aí que mora a velocidade: você nunca olha o lado que não pode conter o valor. Se a busca chega a um lugar vazio (nulo) sem achar, o valor não está na árvore. Essa é a mesma lógica da busca binária numa lista ordenada, mas agora embutida na estrutura.

funcao buscar(no, alvo)
  se no e nulo então
    retorne "não encontrado"
  fim
  se alvo = no.valor então
    retorne "encontrado"
  senão se alvo < no.valor então
    retorne buscar(no.esquerdo, alvo)   // desce à esquerda
  senão
    retorne buscar(no.direito, alvo)    // desce à direita
  fim
fim

A busca compara com o nó e desce para um lado só. Cada comparação elimina um ramo inteiro da árvore.

// BST: 8 na raiz
//        8
//      /   \
//     3     10
//    / \
//   1   6
// buscar o valor 6, contando comparações:
passos <- 0
// no 8: 6 < 8, desce à esquerda   (passos = 1)
// no 3: 6 > 3, desce à direita     (passos = 2)
// no 6: 6 = 6, achou               (passos = 3)
escreva(passos)

A mágica só vale se a árvore estiver equilibrada

Há um porém importante. A busca rápida da BST depende de ela estar equilibrada, ou seja, rasa e bem distribuída. Numa árvore equilibrada com mil valores, achar qualquer um leva cerca de dez passos, porque cada comparação corta o conjunto pela metade. Mas se os valores forem inseridos já em ordem crescente (1, 2, 3, 4...), cada um vira o filho direito do anterior, e a árvore degenera numa linha reta, uma lista disfarçada. Aí a busca volta a ser lenta, passo a passo, sem cortar nada. Por isso existem versões que se reequilibram sozinhas a cada inserção, mantendo a árvore rasa. A ideia central para levar desta aula é: a ordenação por lados dá o potencial de busca rápida, e o equilíbrio é o que garante que esse potencial se realize.