CodeWithBotina
28 de jul. de 2026 10 min de leitura

O que são árvores binárias e por que são tão famosas?

O que são árvores binárias e por que são tão famosas?

Topicos

#árvores binárias #estruturas de dados #BST #AVL #programação #algoritmos #desenvolvimento de software

A maioria das estruturas de dados que aprendemos no início organizam a informação de forma linear: uma lista, um array, uma fila. Mas o mundo real não é linear. O sistema de arquivos do seu computador é hierárquico. O organograma de uma empresa é hierárquico. O DOM de uma página web é hierárquico. Para representar essas estruturas, precisamos de algo mais que uma lista: precisamos de árvores.

Uma árvore binária é a forma mais fundamental e elegante de estrutura hierárquica na computação. É uma estrutura de dados não linear em que cada nó tem no máximo dois filhos, convencionalmente chamados de filho esquerdo e filho direito. Essa restrição — "no máximo dois" — é o que a torna tão poderosa e, ao mesmo tempo, tão gerenciável.

Mas não se engane com sua aparente simplicidade: as árvores binárias são a base dos sistemas de busca mais rápidos (árvores de busca binária), dos motores de banco de dados (B-Trees), da compressão de dados (codificação de Huffman), dos compiladores (árvores de sintaxe abstrata) e até da inteligência artificial (árvores de decisão). Entendê-las não é apenas um exercício acadêmico; é entender como funciona uma parte fundamental do software que você usa diariamente.

Como funciona uma árvore binária?

A estrutura básica

Uma árvore binária é composta por nós. Cada nó contém três elementos fundamentais:

  • Um valor (o dado que armazena)
  • Uma referência ao filho esquerdo
  • Uma referência ao filho direito

O nó superior, do qual toda a árvore pende, é chamado de raiz. Os nós que não têm filhos são chamados de folhas. Os nós intermediários são internos.

Terminologia chave

  • Pai: o nó que está imediatamente acima de outro
  • Filho: o nó que está imediatamente abaixo de outro
  • Irmãos: nós que compartilham o mesmo pai
  • Ancestral: qualquer nó no caminho da raiz até um nó dado
  • Descendente: qualquer nó no caminho de um nó dado até uma folha

Duas métricas essenciais: profundidade e altura

A profundidade de um nó é o comprimento do caminho da raiz até esse nó (contando arestas). A altura de um nó é o comprimento do caminho mais longo desse nó até uma folha. A altura de uma árvore é, portanto, a altura de sua raiz.

flowchart TD
    A["RaizProfundidade: 0"] --> B["Nó internoProfundidade: 1"]
    A --> C["Nó internoProfundidade: 1"]
    B --> D["FolhaProfundidade: 2"]
    B --> E["FolhaProfundidade: 2"]
    C --> F["FolhaProfundidade: 2"]
    C --> G["FolhaProfundidade: 2"]
    
    style A fill:#e3f2fd,stroke:#1565c0
    style B fill:#e8f5e9,stroke:#2e7d32
    style C fill:#e8f5e9,stroke:#2e7d32
    style D fill:#fff3e0,stroke:#ef6c00
    style E fill:#fff3e0,stroke:#ef6c00
    style F fill:#fff3e0,stroke:#ef6c00
    style G fill:#fff3e0,stroke:#ef6c00

Percursos: as três formas de visitar uma árvore binária

Para processar uma árvore binária, precisamos percorrê-la. Existem três percursos clássicos, cada um com uma ordem diferente:

  • Pré-ordem: visita-se o nó raiz, depois a subárvore esquerda, depois a direita.
  • Em-ordem: visita-se a subárvore esquerda, depois a raiz, depois a direita.
  • Pós-ordem: visita-se a subárvore esquerda, depois a direita, depois a raiz.
flowchart LR
    subgraph Preorder["Pré-ordem: A → B → D → E → C → F → G"]
        P1["A"] --> P2["B"]
        P1 --> P3["C"]
        P2 --> P4["D"]
        P2 --> P5["E"]
        P3 --> P6["F"]
        P3 --> P7["G"]
    end

    subgraph Inorder["Em-ordem: D → B → E → A → F → C → G"]
        I1["A"] --> I2["B"]
        I1 --> I3["C"]
        I2 --> I4["D"]
        I2 --> I5["E"]
        I3 --> I6["F"]
        I3 --> I7["G"]
    end

    subgraph Postorder["Pós-ordem: D → E → B → F → G → C → A"]
        O1["A"] --> O2["B"]
        O1 --> O3["C"]
        O2 --> O4["D"]
        O2 --> O5["E"]
        O3 --> O6["F"]
        O3 --> O7["G"]
    end

Por que essa estrutura de dados é tão famosa?

As árvores binárias são famosas por uma razão fundamental: permitem operações em tempo logarítmico quando usadas corretamente. Uma árvore binária balanceada de n nós tem uma altura de O(\log n). Isso significa que buscar, inserir ou remover um elemento em uma árvore de busca binária bem balanceada leva, no pior caso, um tempo proporcional a \log n — muito mais rápido que uma lista encadeada (O(n)) e com uma garantia de desempenho que o hashing nem sempre oferece.

Suas aplicações no mundo real são inúmeras:

  • Sistemas de arquivos: diretórios e subdiretórios são árvores.
  • Bancos de dados: B-Tree e suas variantes são árvores binárias generalizadas.
  • Compiladores: a análise sintática gera árvores de sintaxe abstrata.
  • Inteligência artificial: árvores de decisão são a base de muitos algoritmos de machine learning.
  • Compressão de dados: a codificação de Huffman usa árvores binárias.
  • Redes: algoritmos de roteamento usam árvores.
flowchart LR
    subgraph Applications["Aplicações das árvores binárias"]
        FS["Sistemas de arquivos"]
        DB["Bancos de dados"]
        COMP["Compiladores"]
        AI["Inteligência Artificial"]
        ZIP["Compressão de dados"]
        NET["Redes"]
    end
    
    FS --> BT["Árvores Binárias"]
    DB --> BT
    COMP --> BT
    AI --> BT
    ZIP --> BT
    NET --> BT
    
    style BT fill:#e1f5fe,stroke:#0288d1

Tipos de árvores binárias

Nem todas as árvores binárias são iguais. Existem variantes com propriedades específicas que as tornam adequadas para diferentes problemas.

Árvore binária cheia (Full Binary Tree)

Cada nó tem 0 ou 2 filhos. Nenhum nó tem apenas um filho. Todos os nós internos têm exatamente dois filhos e todas as folhas estão no mesmo nível.

flowchart TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    B --> E["E"]
    C --> F["F"]
    C --> G["G"]

Árvore binária perfeita (Perfect Binary Tree)

É um caso especial de árvore cheia: todos os nós internos têm dois filhos e todas as folhas estão na mesma profundidade. Seu número de nós é 2^{h+1} - 1, onde h é a altura.

Árvore binária completa (Complete Binary Tree)

Todos os níveis, exceto possivelmente o último, estão completamente preenchidos, e os nós do último nível estão o mais à esquerda possível. Esta é a estrutura usada em heaps (montículos).

flowchart TD
    A["A"] --> B["B"]
    A --> C["C"]
    B --> D["D"]
    B --> E["E"]
    C --> F["F"]

Árvore de busca binária (Binary Search Tree - BST)

É uma árvore binária com uma propriedade adicional: para cada nó, todos os valores em sua subárvore esquerda são menores que o valor do nó, e todos os valores em sua subárvore direita são maiores. Isso permite buscas rápidas: a cada passo, você descarta metade da árvore.

Árvore binária balanceada (Balanced Binary Tree)

Uma árvore binária é balanceada se, para cada nó, a altura de suas subárvores esquerda e direita difere em no máximo 1. As variantes mais conhecidas são as árvores AVL e Red‑Black.

Árvore binária inclinada (Skewed Binary Tree)

É o caso degenerado: cada nó tem apenas um filho. Na prática, a árvore se comporta como uma lista encadeada, com complexidade O(n).

flowchart TD
    A["A"] --> B["B"]
    B --> C["C"]
    C --> D["D"]
    D --> E["E"]

Matemática das árvores binárias

Como qualquer estrutura de dados, as árvores binárias podem ser descritas com precisão matemática. Estas são as fórmulas fundamentais.

Número máximo de nós

Em uma árvore binária de altura h (onde a raiz está no nível 0), o número máximo de nós é:

N_{\text{max}} = 2^{h+1} - 1

Isso ocorre porque cada nível i pode ter no máximo 2^i nós.

Número mínimo de nós

O número mínimo de nós para uma altura h é:

N_{\text{min}} = h + 1

Isso ocorre em uma árvore inclinada, onde cada nível tem exatamente um nó.

Relação entre nós e altura

Para uma árvore binária com n nós, a altura mínima possível é:

h_{\text{min}} = \lceil \log_2(n+1) \rceil - 1

E a altura máxima possível é:

h_{\text{max}} = n - 1

Número de nós folha

Em uma árvore binária cheia (onde todo nó tem 0 ou 2 filhos), o número de folhas L e o número de nós internos I satisfazem:

L = I + 1

Esta é uma propriedade fundamental das árvores binárias cheias.

Profundidade média

Para uma árvore de busca binária construída a partir de inserções aleatórias, a profundidade esperada de um nó é aproximadamente:

2 \ln n \approx 1.39 \log_2 n

Isso explica por que BSTs aleatórias funcionam tão bem na prática, mesmo sem balanceamento explícito.

Árvores binárias em código

Vamos ver como implementar uma árvore binária nas linguagens mais populares. Todos os exemplos compartilham a mesma estrutura: uma classe Node com um valor e duas referências para os filhos.

Java

public class BinaryTree {
    static class Node {
        T value;
        Node left;
        Node right;
        
        Node(T value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }
    
    private Node root;
    
    public BinaryTree() {
        this.root = null;
    }
    
    // Percurso em pré-ordem
    public void preorder() {
        preorder(root);
    }
    
    private void preorder(Node node) {
        if (node == null) return;
        System.out.print(node.value + " ");
        preorder(node.left);
        preorder(node.right);
    }
}

Python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
    
    def __repr__(self):
        return f"Node({self.value})"

class BinaryTree:
    def __init__(self):
        self.root = None
    
    def preorder(self, node=None):
        if node is None:
            node = self.root
        if node is None:
            return
        print(node.value, end=" ")
        self.preorder(node.left)
        self.preorder(node.right)

JavaScript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }
    
    preorder(node = this.root) {
        if (node === null) return;
        console.log(node.value);
        this.preorder(node.left);
        this.preorder(node.right);
    }
}

C#

public class BinaryTree
{
    public class Node
    {
        public T Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        
        public Node(T value)
        {
            Value = value;
            Left = null;
            Right = null;
        }
    }
    
    private Node _root;
    
    public BinaryTree()
    {
        _root = null;
    }
    
    public void Preorder()
    {
        Preorder(_root);
    }
    
    private void Preorder(Node node)
    {
        if (node == null) return;
        Console.Write(node.Value + " ");
        Preorder(node.Left);
        Preorder(node.Right);
    }
}

Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: T,
    left: Option>>>,
    right: Option>>>,
}

impl Node {
    fn new(value: T) -> Rc> {
        Rc::new(RefCell::new(Node {
            value,
            left: None,
            right: None,
        }))
    }
}

struct BinaryTree {
    root: Option>>>,
}

impl BinaryTree {
    fn new() -> Self {
        BinaryTree { root: None }
    }
}

A enquete: qual estrutura de dados você escolheria?

Imagine que você está construindo um sistema que precisa lidar com dados hierárquicos com operações frequentes de busca, inserção e remoção, e você precisa que o desempenho seja previsível e eficiente mesmo no pior caso. Qual estrutura de dados você escolheria?

Qual estrutura de dados você usaria para este problema?

Referências

1 Curtir 0 Nao curtir 1 total

Carregando reacoes...

Comentarios (0)

Carregando sessao...

Ainda nao ha comentarios. Seja o primeiro a comentar.
Voltar para todos os posts