Algoritmos

Árvore binária: dois caminhos por nó para achar mais rápido

Capa do artigo Árvore binária: dois caminhos por nó para achar mais rápido
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona uma árvore binária?
  2. O que é uma árvore binária de busca?
  3. Árvore binária de busca em PHP, Python, C e Java
  4. Por que a busca em uma árvore é rápida?
  5. Onde as árvores aparecem no dia a dia?
  6. Agora é com você!

Árvore binária é uma estrutura de dados em que cada nó guarda um valor e pode ter até dois filhos: um à esquerda e um à direita. Ela começa em um único nó, chamado raiz, e vai se ramificando para baixo.

No artigo sobre fila, o desafio era criar o método espiar. A resposta: ele devolve o valor do nó que está no início, sem mexer em nenhuma referência. E se a fila estiver vazia, devolve “nada” (null em PHP, None em Python). Era só isso! Se você pensou em algo parecido, está no caminho certo.

Lista, pilha e fila são estruturas “em linha”. Hoje a história muda, e você verá a recursividade brilhar, como eu tinha prometido!

Como funciona uma árvore binária?

Pense em uma árvore genealógica desenhada de cima para baixo: no topo está uma pessoa, abaixo dela os filhos, abaixo de cada filho os filhos dele, e assim vai. Na árvore binária a ideia é a mesma, com uma regra: cada nó tem no máximo dois filhos.

Árvore genealógica com Ana no topo, os filhos Bia e Caio abaixo e os netos Duda, Enzo e Fábio, com as indicações de raiz, filho à esquerda, filho à direita, subárvore e folha
A família da Ana tem a forma de uma árvore binária: ninguém tem mais de dois filhos.

Alguns nomes que você ouvirá sempre:

  • Raiz: o nó do topo, por onde tudo começa.
  • Filho: o nó ligado logo abaixo de outro. Cada nó pode ter um filho à esquerda e um à direita.
  • Folha: o nó que não tem filhos.
  • Subárvore: qualquer nó junto com tudo o que está abaixo dele. Guarde isso: cada subárvore também é uma árvore!

O que é uma árvore binária de busca?

É uma árvore binária que segue uma regra de organização: para qualquer nó, os valores menores ficam à esquerda e os maiores ficam à direita. Veja a árvore que se forma quando inserimos os valores 50, 30, 70, 20, 40, 60 e 80, nessa ordem:

Árvore binária de busca com raiz 50, filhos 30 e 70 e folhas 20, 40, 60 e 80
Árvore binária de busca formada pelos valores 50, 30, 70, 20, 40, 60 e 80.
ValorCaminho percorridoOnde fica
50A árvore está vaziaVira a raiz
30Menor que 50À esquerda do 50
70Maior que 50À direita do 50
20Menor que 50, menor que 30À esquerda do 30
40Menor que 50, maior que 30À direita do 30
60Maior que 50, menor que 70À esquerda do 70
80Maior que 50, maior que 70À direita do 70
Passo a passo da inserção de cada valor na árvore.
Ver a animação da inserção e da busca na árvore
Animação da inserção dos valores 50, 30, 70, 20, 40, 60 e 80 em uma árvore binária de busca, seguida da busca pelo valor 60
Cada valor desce pela árvore comparando com os nós do caminho. No fim, a busca pelo 60 segue a mesma regra.

Árvore binária de busca em PHP, Python, C e Java

O código tem duas funções. A de inserir desce pela árvore comparando valores até achar um lugar vazio. A de percorrer em ordem visita primeiro tudo o que está à esquerda, depois o próprio nó e por último tudo o que está à direita. Veja em PHP:

<?php

class No
{
    public ?No $esquerda = null;
    public ?No $direita = null;

    public function __construct(public int $valor)
    {
    }
}

function inserir(?No $no, int $valor): No
{
    if ($no === null) {
        return new No($valor); // achou o lugar vazio: o nó nasce aqui
    }

    if ($valor < $no->valor) {
        $no->esquerda = inserir($no->esquerda, $valor);
    } else {
        $no->direita = inserir($no->direita, $valor);
    }

    return $no;
}

function emOrdem(?No $no): void
{
    if ($no === null) {
        return; // caso base: não há nó para visitar
    }

    emOrdem($no->esquerda);
    echo $no->valor, ' ';
    emOrdem($no->direita);
}

$raiz = null;

foreach ([50, 30, 70, 20, 40, 60, 80] as $valor) {
    $raiz = inserir($raiz, $valor);
}

emOrdem($raiz); // 20 30 40 50 60 70 80
echo PHP_EOL;

Em Python:

class No:
    def __init__(self, valor):
        self.valor = valor
        self.esquerda = None
        self.direita = None


def inserir(no, valor):
    if no is None:
        return No(valor)  # achou o lugar vazio: o nó nasce aqui

    if valor < no.valor:
        no.esquerda = inserir(no.esquerda, valor)
    else:
        no.direita = inserir(no.direita, valor)

    return no


def em_ordem(no):
    if no is None:
        return  # caso base: não há nó para visitar

    em_ordem(no.esquerda)
    print(no.valor, end=" ")
    em_ordem(no.direita)


raiz = None

for valor in [50, 30, 70, 20, 40, 60, 80]:
    raiz = inserir(raiz, valor)

em_ordem(raiz)  # 20 30 40 50 60 70 80
print()

E em C:

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

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

struct No *inserir(struct No *no, int valor) {
    if (no == NULL) {
        struct No *novo = malloc(sizeof(struct No));

        if (novo == NULL) {
            return NULL; // sem memória
        }

        novo->valor = valor;
        novo->esquerda = NULL;
        novo->direita = NULL;
        return novo; // achou o lugar vazio: o nó nasce aqui
    }

    if (valor < no->valor) {
        no->esquerda = inserir(no->esquerda, valor);
    } else {
        no->direita = inserir(no->direita, valor);
    }

    return no;
}

void em_ordem(struct No *no) {
    if (no == NULL) {
        return; // caso base: não há nó para visitar
    }

    em_ordem(no->esquerda);
    printf("%d ", no->valor);
    em_ordem(no->direita);
}

void liberar(struct No *no) {
    if (no == NULL) {
        return;
    }

    liberar(no->esquerda);
    liberar(no->direita);
    free(no); // em C, você devolve a memória de cada nó
}

int main(void) {
    int valores[] = {50, 30, 70, 20, 40, 60, 80};
    struct No *raiz = NULL;

    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;
}

E em Java:

public class Main {
    static class No {
        int valor;
        No esquerda;
        No direita;

        No(int valor) {
            this.valor = valor;
        }
    }

    static No inserir(No no, int valor) {
        if (no == null) {
            return new No(valor); // achou o lugar vazio: o nó nasce aqui
        }
        if (valor < no.valor) {
            no.esquerda = inserir(no.esquerda, valor);
        } else {
            no.direita = inserir(no.direita, valor);
        }
        return no;
    }

    static void emOrdem(No no) {
        if (no == null) {
            return; // caso base: não há nó para visitar
        }
        emOrdem(no.esquerda);
        System.out.print(no.valor + " ");
        emOrdem(no.direita);
    }

    public static void main(String[] args) {
        int[] valores = {50, 30, 70, 20, 40, 60, 80};
        No raiz = null;
        for (int valor : valores) {
            raiz = inserir(raiz, valor);
        }
        emOrdem(raiz); // 20 30 40 50 60 70 80
        System.out.println();
    }
}

Reparou no resultado? Os valores saíram em ordem crescente, e não usei nenhum algoritmo de ordenação!!! A regra dos menores à esquerda e dos maiores à direita já deixa tudo no lugar.

E as duas funções são recursivas. Lembra que cada subárvore também é uma árvore? É por isso que a recursividade encaixa tão bem aqui: a função resolve um nó e chama a si mesma para os filhos. O caso base é chegar em um lugar vazio.

Um detalhe: neste exemplo, um valor repetido vai para a direita. É uma escolha, e o importante é usar sempre a mesma regra.

Por que a busca em uma árvore é rápida?

Para procurar o 60 na árvore do desenho, você começa na raiz: 60 é maior que 50, então vai para a direita e esquece tudo o que está à esquerda. Chegou no 70: 60 é menor, vai para a esquerda. Achou! Foram 3 comparações em uma árvore de 7 valores.

Árvore binária de busca com o caminho da busca pelo 60 em destaque: 50, depois 70, depois 60, e os demais nós tracejados
A busca pelo 60 visita três nós. Os outros quatro nem são olhados.

Isso lembra alguma coisa? É a mesma ideia da busca binária: em uma árvore bem distribuída, cada comparação descarta perto de metade do que sobrou.

Valores na árvoreMáximo de comparações
73
1.02310
1.048.57520
Máximo de comparações em uma árvore com todos os níveis completos.

ATENÇÃO para um detalhe: a árvore só é rápida se estiver bem distribuída. Se você inserir os valores já em ordem (10, 20, 30, 40…), cada um vai sempre para a direita do anterior, e a árvore vira uma “linha”, igual a uma lista encadeada. Aí a busca volta a ser nó por nó.

Duas árvores com os valores de 10 a 70: uma distribuída em três níveis e outra em forma de lista, com sete níveis
A ordem de inserção muda o formato da árvore, e o formato muda a velocidade da busca.

Para evitar isso existem as árvores balanceadas, como a AVL e a rubro-negra, que se reorganizam sozinhas. Mas isso é assunto para depois. Um passo de cada vez!

Só para você ver uma delas trabalhando: no Java, a classe TreeMap é baseada em uma árvore rubro-negra, e a TreeSet é construída sobre ela. Com a TreeSet, os mesmos sete valores saem em ordem sem você escrever a árvore:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> valores = new TreeSet<>();
        for (int valor : new int[] {50, 30, 70, 20, 40, 60, 80}) {
            valores.add(valor);
        }
        System.out.println(valores);              // [20, 30, 40, 50, 60, 70, 80]
        System.out.println(valores.contains(60)); // true
    }
}

Onde as árvores aparecem no dia a dia?

As pastas do seu computador formam uma árvore: uma pasta tem outras pastas dentro, que têm outras… As tags de uma página HTML também. Essas árvores não são binárias, porque um nó pode ter vários filhos, mas a ideia de raiz, filhos e folhas é exatamente a mesma. Quem entende a árvore binária entende as outras com muito mais facilidade.

Agora é com você!

Pegue papel e caneta e insira os valores 45, 25, 65, 10 e 30, nessa ordem, em uma árvore binária de busca vazia. Desenhe o resultado. Depois responda: quais nós são folhas? E em que sequência o percurso em ordem mostra os valores?

Desenhar no papel antes de rodar o código é um dos melhores treinos que existem. Não pule essa etapa, e não peça o desenho pronto para ninguém! A resposta vem no próximo artigo.

E nele vamos conhecer a tabela hash, a estrutura que consegue achar um valor quase sem procurar. Até lá!

Confiança Sempre!!!

Fontes:

Compartilhe este artigo

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Guardamos o IP e o navegador de quem comenta por 6 meses, para barrar spam e porque o Marco Civil da Internet pede a guarda dos registros de acesso por esse prazo. Veja como tratamos seus dados.

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e o código do registro dela, e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager.

Exibem anúncios do Google AdSense sem personalização. Os cookies desta categoria limitam a repetição dos anúncios e medem o resultado deles.

Usa a sua navegação para escolher anúncios e formar públicos de anúncio: anúncios do Google escolhidos pelos seus interesses e os indicadores do Google no Analytics. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.