Conceito inicial

Quando precisamos manter uma coleção de valores ordenados e realizar consultas rápidas, listas simples podem ser insuficientes. Uma árvore de busca binária (BST) organiza os dados de modo que cada valor possa ser localizado descendo por apenas um dos ramos, reduzindo drasticamente o número de comparações necessárias.

Regras da estrutura

• Cada nó possui, no máximo, dois filhos: um à esquerda e outro à direita.
• Para qualquer nó, todos os valores contidos na subárvore esquerda são menores do que o valor do próprio nó.
• Todos os valores da subárvore direita são maiores do que o valor do nó.
• Essa propriedade vale para todos os nós, não apenas para a raiz.

Terminologia básica

• Raiz: nó inicial da árvore.
• Folha: nó sem filhos.
• Nível: distância de um nó até a raiz, contada em arestas.
• Altura: maior nível existente na árvore.
• Balenceamento: diferença entre as alturas das subárvores esquerda e direita de um nó.

Representando os nós

O primeiro passo para implementar uma BST é definir a classe de nó. Abaixo, chave representa o valor armazenado, enquanto esquerda e direita apontam para os filhos.

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

Construindo e inserindo valores

Para manter as regras da BST, cada novo valor deve ser inserido comparando-o ao nó atual e descendo pelo ramo adequado.

class ArvoreBuscaBinaria:
    def __init__(self):
        self.raiz = None

    def inserir(self, chave):
        if self.raiz is None:
            self.raiz = No(chave)
        else:
            self._inserir_rec(self.raiz, chave)

    def _inserir_rec(self, no, chave):
        if chave < no.chave:
            if no.esquerda is None:
                no.esquerda = No(chave)
            else:
                self._inserir_rec(no.esquerda, chave)
        elif chave > no.chave:
            if no.direita is None:
                no.direita = No(chave)
            else:
                self._inserir_rec(no.direita, chave)
        # Valores iguais são ignorados nesta implementação.

Algoritmo de busca

A busca aproveita a ordenação interna: se o valor procurado for menor que o nó atual, continua-se pela esquerda; caso contrário, pela direita. O processo se repete até encontrar o valor ou chegar a um ramo vazio.

    def buscar(self, chave):
        return self._buscar_rec(self.raiz, chave)

    def _buscar_rec(self, no, chave):
        if no is None or no.chave == chave:
            return no
        if chave < no.chave:
            return self._buscar_rec(no.esquerda, chave)
        return self._buscar_rec(no.direita, chave)

Eficiência da busca

Em uma árvore bem balanceada, cada comparação descarta aproximadamenet metade dos nós restantes. Por isso, a busca costuma ter complexidade O(log n). Se a árvore estiver degenerada — semelhante a uma lista encadeada — a complexidade se torna O(n).

Remoção de nós

Remover um nó exige cuidado para preservar a ordenação. Há três situações:

• Folha: basta removê-lo.
• Um filho: o filho ocupa o lugar do nó removido.
• Dois filhos: substitui-se o nó pelo seu sucessor, ou seja, o menor valor da subárvore direita.

    def remover(self, chave):
        self.raiz = self._remover_rec(self.raiz, chave)

    def _remover_rec(self, no, chave):
        if no is None:
            return no

        if chave < no.chave:
            no.esquerda = self._remover_rec(no.esquerda, chave)
        elif chave > no.chave:
            no.direita = self._remover_rec(no.direita, chave)
        else:
            if no.esquerda is None:
                return no.direita
            if no.direita is None:
                return no.esquerda

            sucessor = self._menor(no.direita)
            no.chave = sucessor.chave
            no.direita = self._remover_rec(no.direita, sucessor.chave)

        return no

    def _menor(self, no):
        while no.esquerda is not None:
            no = no.esquerda
        return no

Percurso dos elementos

O percurso em ordem (in-order) visita primeiro a subárvore esquerda, depois o nó atual e, por fim, a subárvore direita. Em uma BST, esse percurso retorna os valores ordenados.

    def em_ordem(self):
        resultado = []
        self._em_ordem_rec(self.raiz, resultado)
        return resultado

    def _em_ordem_rec(self, no, resultado):
        if no:
            self._em_ordem_rec(no.esquerda, resultado)
            resultado.append(no.chave)
            self._em_ordem_rec(no.direita, resultado)

Outros percursos comuns incluem:

• Pré-ordem: visita o nó atual antes dos filhos.
• Pós-ordem: visita os filhos antes do nó atual.

Cenários de uso

• Índices de bancos de dados que precisam manter registros ordanados.
• Implementação de mapas e conjuntos ordenados.
• Sistemas de autocomplete e autocompletar com prefixos.
• Qualquer aplicação que exija busca, inserção e remoção frequentes de dados dinâmicos.