Árvores Binárias | Blog | Vinicius Henrique Portfolio

Árvores Binárias de Busca - BST (Binary Search Tree)

Se você está dando seus primeiros passos no desenvolvimento de softwares ou se preparando para aquelas temidas entrevistas técnicas, existe um momento crucial que desafia sua mente. É o momento em que você deixa de apenas "guardar dados" e passa a organizar os dados com inteligência.

Até agora, as suas ferramentas favoritas provavelmente foram os arrays (listas) e os objetos. Mas o que acontece quando sua aplicação cresce e você precisa buscar um registro específico no meio de 10 milhões de linhas em uma lista desordenada?

Se você utilizar um array estruturado de forma desordenada, o seu sistema precisará ler linha a linha. No pior dos casos, serão 10 milhões de operações. O seu servidor irá se sobrecarregar, a experiência do usuário será ruim e o seu hardware vai pagar a conta.

E é exatamente o problema de velocidade e escala que as estruturas de dados não lineares existem. E hoje iremos abordar uma das estruturas mais importantes desse universo: a Árvore Binária de Busca (BST).

Abaixo irei responder as seguintes dúvidas:

O que é uma Árvore Binária de Busca(Binary Search Tree)?
O que significa dizer que a busca em uma árvore é O(log n)?
O que é uma "árvore degenerada" e por que ela arruína a performance?
Por que criaram as Árvores AVL e Red-Black se a árvore binária comum já existia?
Onde as árvores binárias são usadas na prática no mercado de trabalho?

O que é uma Arvore Binária de Busca (Binary Search Tree)?

Antes de entender uma Árvore Binária de Busca (BST), precisamos compreender o conceito de Árvore Binária.

Diferentemente de um array (lista), que armazena elementos de forma linear, uma árvore binária organiza os dados em uma estrutura hierárquica composta por nós. Cada nó pode possuir no máximo dois filhos: um filho à esquerda e um filho à direita.

Uma Árvore Binária de Busca é um tipo especial de árvore binária que segue uma regra simples de organização:

Todos os valores menores que um nó ficam em sua subárvore esquerda;
Todos os valores maiores que um nó ficam em sua subárvore direita.

Cada elemento armazenado na árvore recebe o nome de nó (node). Um nó guarda um valor e referências para seus filhos esquerdo e direito.

Propriedades do Nó:

class No {

    valor: number;
    esquerda: No | null;
    direita: No | null;

    constructor(valor: number){
        this.valor = valor;
        this.esquerda = null;
        this.direita = null;
    }
}

Implementação de Árvore Binária em Typescript:

class Arvore {

    raiz: No | null;

    constructor () {
        this.raiz = null;
    }

    public insert(valor: number): void {
        if(this.raiz == null) {
            this.raiz = new No(valor);
            console.log(`Valor ${valor} alocado na raiz`)
        } else {
            this.recursiveInsert(this.raiz, valor)
        }
    }

    private recursiveInsert(raiz: No,valor: number): void {
        if(valor == raiz.valor){
            console.log(`O valor ${valor} já existe!`);
            return
        } else if(valor < raiz.valor){
            if(raiz.esquerda == null){
                raiz.esquerda = new No(valor);
                console.log(`Valor ${valor} alocado a esquerda de ${raiz.valor}`)
            } else {
                this.recursiveInsert(raiz.esquerda, valor)
            }
        } else {
            if(raiz.direita == null){
                raiz.direita = new No(valor);
                console.log(`Valor ${valor} alocado a direita de ${raiz.valor}`)
            } else {
                this.recursiveInsert(raiz.direita, valor);
            }
        }
    }
}

Por exemplo, ao inserir os valores 50, 30, 70, 20 e 40, a estrutura resultante seria:

          50
        /    \
      30      70
     /  \    /  \
   20   40 60   80

Principais operações em uma BST

Inserção: adiciona novos elementos respeitando as regras da árvore.
Busca: localiza um elemento percorrendo os nós.
Remoção: remove um elemento preservando a estrutura da árvore. Em uma árvore balanceada, essa propriedade permite descartar aproximadamente metade das possibilidades a cada comparação durante uma busca, o que torna a operação muito mais eficiente do que uma busca sequencial em uma coleção não ordenada.

O que significa dizer que a busca em uma árvore é O(log n)?

Quando falamos que a busca em uma Árvore Binária de Busca possuí complexidade O(log n), estamos descrevendo quanto tempo é necessário para encontrar um elemento a medida que a quantidade de dados cresce.

O termo log n surge porque, a cada comparação realizada durante a busca, podemos descartar aproximadamente metade dos elementos restantes.

Imagine que estamos procurando o elemento 75 logo abaixo:

O algoritmo começa no nó raiz (50).

Como 75 é maior que 50, ignoramos toda a subárvore esquerda;
Em seguida, chegamos ao nó 100;
Como 75 é menor que 100, ignoramos toda a subárvore direita;
Finalmente, chegamos ao nó 75.

Observe que não foi necessário visitar todos os elementos da estrutura. Em cada passo, uma grande parte da árvore foi descartada da busca.

É exatamente esse comportamento que torna as BSTs tão eficientes. Enquanto uma busca sequencial em uma coleção não ordenada pode exigir até n comparações no pior caso (O(n)), uma árvore bem balanceada reduz drasticamente essa quantidade para aproximadamente log₂(n) comparações.

Para ter uma ideia:

Quantidade de elementos	Comparações aproximadas em O(log₂ n)
1.000	10
1.000.000	20
1.000.000.000	30

Isso significa que, mesmo com bilhões de elementos, o número de comparações continua relativamente pequeno. É essa característica que torna as árvores uma das estruturas fundamentais para a construção de sistemas que precisam realizar buscas de forma eficiente.

O que é uma "Árvore Degenerada" e por que ela arruína a performance?

Até agora vimos que uma Árvore Binária de Busca pode realizar buscas em O(log n). No entanto, isso só acontece quando a árvore está razoavelmente balanceada.

Existe um cenário em que a BST perde completamente sua eficiência: quando ela se transforma em uma Árvore Degenerada.

Uma árvore degenerada ocorre quando os nós são inseridos em uma ordem que faz com que cada elemento possua apenas um filho, transformando a estrutura em algo muito parecido com uma lista encadeada.

Por exemplo, imagine que inserimos os seguintes valores em ordem crescente:

10, 20, 30, 40, 50

A árvore resultante será:

Observe que não existe mais uma divisão equilibrada dos dados. Todos os nós foram inseridos para a direita, formando uma espécie de "corrente".

Agora imagine que queremos encontrar o valor 50.

O algoritmo precisará percorrer:

10 → 20 → 30 → 40 → 50

Nesse caso, foram necessárias 5 comparações para encontrar o elemento.

Se a árvore possuir 1 milhão de nós organizados dessa forma, o algoritmo poderá precisar percorrer praticamente todos eles.

Em outras palavras, a complexidade da busca deixa de ser O (log n) para ser O(n), sendo o mesmo comportamento de uma busca sequencial em uma lista comum.

É por esse motivo que árvores binárias de busca simples raramente são utilizadas sozinhas em sistemas que exigem alta performance. Na prática, é necessário garantir que a árvore permaneça balanceada para evitar que ela se transforme em uma árvore degenerada.

Foi justamente para resolver esse problema que surgiram estruturas como as Árvores AVL e as Árvores Red-Black, que realizam ajustes automáticos após inserções e remoções para manter a altura da árvore sob controle.

Por que criaram as Árvores AVL e Red-Black se a árvore binária comum já existia?

Como vimos na seção anterior, uma BST comum pode oferecer buscas extremamente rápidas quando está balanceada. O problema é que ela não possui nenhum mecanismo para garantir que esse balanceamento seja mantido ao longo do tempo.

À medida que novos elementos são inseridos, a árvore pode crescer de forma desigual e acabar se transformando em uma árvore degenerada. Quando isso acontece, operações de busca, inserção e remoção deixam de ter desempenho O(*log n*) e passam a apresentar comportamento O(*n*).

Foi justamente para resolver esse problema que surgiram as chamadas árvores auto-balanceadas.

Essas estruturas aplicam regras adicionais e realizam reorganizações automáticas, conhecidas como rotações, sempre que detectam que a árvore está ficando desequilibrada. O objetivo é manter sua altura próxima do ideal e preservar a eficiência das operações.

As duas implementações mais conhecidas são as Árvores AVL e as Árvores Red-Black.

Árvores AVL

As Árvores AVL foram as primeiras árvores binárias de busca auto-balanceadas da história, propostas em 1962 pelos matemáticos soviéticos Georgy Adelson-Velsky e Evgenii Landis.

Sua principal característica é manter um balanceamento bastante rígido. Para cada nó, a diferença de altura entre as subárvores esquerda e direita não pode ser maior que 1.

Por causa desse controle rigoroso, as árvores AVL tendem a possuir menor altura, resultando em buscas ligeiramente mais rápidas.

Por outro lado, inserções e remoções podem exigir mais rotações para restaurar o equilíbrio da estrutura.

Árvores Red-Black

As Árvores Red-Black adotam uma estratégia diferente. Em vez de controlar exatamente a altura de cada subárvore, elas utilizam regras baseadas em cores atribuídas aos nós.

Essas regras permitem um balanceamento menos rigoroso, mas ainda suficientemente eficiente para garantir que a altura da árvore permaneça proporcional a log n.

Como consequência, operações de inserção e remoção geralmente exigem menos ajustes do que em uma AVL, tornando as Árvores Red-Black uma escolha muito popular em bibliotecas, sistemas operacionais e bancos de dados.

AVL vs Red-Black

De forma simplificada:

Característica	AVL	Red-Black
Balanceamento	Mais rigoroso	Mais flexível
Velocidade de busca	Geralmente melhor	Muito boa
Inserções e remoções	Mais rotações	Menos rotações
Uso em bibliotecas e sistemas	Menos comum	Muito comum

Na prática, ambas existem para resolver exatamente o mesmo problema: impedir que uma árvore binária de busca se transforme em uma árvore degenerada e perca sua eficiência.

Graças a esses mecanismos de auto-balanceamento, operações fundamentais como busca, inserção e remoção continuam apresentando desempenho próximo de O(log n) mesmo quando a estrutura cresce para milhares ou milhões de elementos.

A BST nos ensina como organizar dados de forma hierárquica e eficiente. Já as árvores AVL e Red-Black mostram que, em computação, não basta encontrar uma solução rápida; é preciso garantir que ela continue rápida independentemente de como os dados evoluem ao longo do tempo.

Onde as árvores binárias são usadas na prática no mercado de trabalho?

Depois de estudar BSTs, AVL e Red-Black, uma dúvida muito comum surge:

"Mas eu realmente vou usar isso no meu dia a dia como desenvolvedor?"

A resposta é: sim, mas nem sempre de forma explícita.

Na maioria dos casos, você não precisará implementar uma árvore binária do zero. Entretanto, diversas ferramentas, bibliotecas e sistemas que você utiliza diariamente dependem dessas estruturas internamente.

Alguns exemplos são:

Bancos de Dados

Bancos de dados precisam localizar registros rapidamente mesmo quando armazenam milhões de linhas.

Para isso, utilizam estruturas de indexação baseadas em árvores balanceadas, especialmente variantes das B-Trees e B+ Trees, que seguem a mesma ideia fundamental das BSTs: organizar os dados de forma hierárquica para reduzir drasticamente o número de comparações necessárias durante uma busca.

Quando você executa uma consulta como:

SELECT * FROM usuarios
WHERE id = 1000;

há uma grande chance de que um índice baseado em árvores esteja ajudando o banco a encontrar esse registro sem precisar percorrer toda a tabela.

Linguagens de Programação

Diversas linguagens utilizam árvores balanceadas para implementar coleções ordenadas.

Por exemplo:

TreeMap e TreeSet no Java utilizam árvores Red-Black;
std::map e std::set em C++ normalmente são implementados com Red-Black Trees;
Muitas bibliotecas de estruturas ordenadas em outras linguagens seguem a mesma abordagem.

Essas coleções conseguem manter os elementos ordenados enquanto oferecem buscas, inserções e remoções eficientes.

Sistemas Operacionais

Sistemas operacionais modernos utilizam árvores balanceadas para gerenciar recursos internos, como:

Escalonamento de processos;
Gerenciamento de memória;
Estruturas de controle do kernel;
Controle de timers e eventos.

O kernel Linux, por exemplo, utiliza Árvores Red-Black em diversos subsistemas devido ao seu excelente equilíbrio entre desempenho e custo de manutenção.

Sistemas de Arquivos

Estruturas de árvore também são amplamente utilizadas para organizar diretórios e localizar arquivos rapidamente.

Embora os sistemas de arquivos modernos utilizem variações mais sofisticadas, o conceito continua sendo o mesmo: dividir os dados hierarquicamente para tornar as buscas mais eficientes.

Motores de Busca e Sistemas de Indexação

Sempre que um sistema precisa localizar informações rapidamente dentro de grandes volumes de dados, estruturas de árvore costumam aparecer.

Motores de busca, sistemas de recomendação, plataformas de e-commerce e ferramentas de análise de dados frequentemente utilizam árvores e estruturas derivadas para indexação e recuperação eficiente de informações.

O que você deve levar deste artigo?

O mais importante não é decorar cada tipo de árvore ou suas regras de balanceamento.

O principal aprendizado é compreender o problema que essas estruturas resolvem: como organizar dados de forma que as operações continuem rápidas mesmo quando o volume de informações cresce para milhões ou bilhões de registros.

As BSTs apresentam a ideia fundamental. As árvores AVL e Red-Black mostram como preservar essa eficiência na prática. E, a partir delas, surgiram diversas outras estruturas utilizadas em bancos de dados, sistemas operacionais e aplicações de larga escala que utilizamos todos os dias.

Conclusão

As Árvores Binárias de Busca foram uma das primeiras estruturas criadas para resolver um problema fundamental da computação: encontrar informações rapidamente em grandes volumes de dados.

Embora uma BST simples possa perder eficiência quando se torna degenerada, ela introduz conceitos que serviram de base para estruturas mais avançadas, como AVL Trees, Red-Black Trees e B-Trees, utilizadas até hoje em bancos de dados, sistemas operacionais e bibliotecas de programação.

Entender BSTs não é apenas aprender uma estrutura de dados. É compreender um dos princípios mais importantes da engenharia de software: organizar dados corretamente é tão importante quanto armazená-los.