Á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.
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 formada pelos valores 50, 30, 70, 20, 40, 60 e 80.
Valor
Caminho percorrido
Onde fica
50
A árvore está vazia
Vira a raiz
30
Menor que 50
À esquerda do 50
70
Maior que 50
À direita do 50
20
Menor que 50, menor que 30
À esquerda do 30
40
Menor que 50, maior que 30
À direita do 30
60
Maior que 50, menor que 70
À esquerda do 70
80
Maior 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
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.
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 árvore
Máximo de comparações
7
3
1.023
10
1.048.575
20
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ó.
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á!
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.
Usamos cookies necessários para o site funcionar. Com a sua permissão, também usamos cookies de estatística e de publicidade, com ou sem personalização. Você pode mudar a escolha quando quiser em Preferências de cookies. Política de privacidade
Continue a conversa