Pular para o conteúdo
Felipe Túlio

Árvores binárias de busca: busca, inserção e remoção

9 min de leituraProgramação

Uma árvore binária de busca (ABB) é uma árvore binária em que as chaves estão organizadas de modo que cada nó separe as chaves menores, à esquerda, das maiores, à direita. Essa regra transforma a árvore em um índice: para localizar uma chave, não é preciso examinar todos os nós, apenas seguir um caminho da raiz até um nó ou até uma posição vazia (Cormen et al., 2022). Neste artigo, estudamos como buscar uma chave e como modificar a árvore por inserção e por remoção, sempre preservando a regra de ordenação. Todos os códigos usam C++17 e ponteiros próprios, sem bibliotecas prontas para árvores.

Adotamos duas simplificações: as chaves são inteiros e não há chaves repetidas. A segunda escolha importa: com duplicatas, a convenção sobre qual lado recebe a chave igual afeta a inserção e a escolha do substituto na remoção (OpenDSA Project Contributors, 2023).

Fundamentos: a propriedade da ABB

Cada nó guarda uma chave e dois ponteiros, um para o filho esquerdo e outro para o direito; nullptr indica ausência de filho. A propriedade da ABB afirma que, para todo nó x:

  • todas as chaves da subárvore esquerda de x são menores que a chave de x;
  • todas as chaves da subárvore direita de x são maiores que a chave de x.

A propriedade vale para todos os descendentes, não só para os filhos imediatos. Um erro comum é conferir apenas a relação entre pai e filho: na Figura 1, colocar 9 como filho direito de 6 respeitaria a relação local (9 > 6), mas violaria a regra, pois 9 está na subárvore esquerda de 8 e é maior que 8.

Usaremos um exemplo contínuo: uma coleção de identificadores de tarefas inseridos na ordem 8, 4, 12, 2, 6, 10 e 14.

Figura 1. ABB inicial, com as chaves 8, 4, 12, 2, 6, 10 e 14.

flowchart TD
    A["8"] -->|esq| B["4"]
    A -->|dir| C["12"]
    B -->|esq| D["2"]
    B -->|dir| E["6"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]

Na Figura 1, as chaves à esquerda de 8 (2, 4, 6) são menores que 8, e as da direita (10, 12, 14) são maiores. A mesma regra vale dentro de cada subárvore. Uma consequência útil é que o percurso em ordem (esquerda, nó, direita) visita as chaves em ordem crescente: 2, 4, 6, 8, 10, 12, 14 (OpenDSA Project Contributors, 2023). Usaremos essa propriedade para conferir se as operações preservam a ABB.

O código abaixo define o nó. O construtor inicializa os ponteiros com nullptr, de modo que todo nó novo nasce como folha.

#include <iostream>
#include <vector>

struct No {
    int chave;
    No* esq;
    No* dir;
    explicit No(int c) : chave(c), esq(nullptr), dir(nullptr) {}
};

Busca

A busca aproveita a propriedade da ABB para descartar uma subárvore inteira a cada comparação. Partindo da raiz, comparamos a chave procurada k com a chave do nó atual:

  1. se forem iguais, a busca termina com sucesso;
  2. se k for menor, o único lugar possível é a subárvore esquerda;
  3. se k for maior, o único lugar possível é a subárvore direita;
  4. se chegarmos a nullptr, a chave não existe na árvore.

Figura 2. Caminho percorrido na busca pela chave 6 (nós em destaque).

flowchart TD
    A["8"] -->|esq| B["4"]
    A -->|dir| C["12"]
    B -->|esq| D["2"]
    B -->|dir| E["6"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]
    classDef caminho fill:#fde68a,stroke:#b45309,stroke-width:2px
    class A,B,E caminho

Para k = 6: 6 < 8, desce para 4; 6 > 4, desce para 6; 6 = 6, encontrado. Foram três comparações, em vez de até sete. Para k = 5, o caminho seria 8, 4, 6 e, como 5 < 6, chegaríamos ao filho esquerdo de 6, que é nullptr: a busca termina sem sucesso, e essa posição vazia é exatamente onde 5 deveria ser inserido.

A versão iterativa a seguir devolve o ponteiro para o nó ou nullptr. O laço usa a condição de parada conjunta (nó vazio ou chave encontrada).

No* buscar(No* raiz, int chave) {
    while (raiz != nullptr && raiz->chave != chave) {
        raiz = (chave < raiz->chave) ? raiz->esq : raiz->dir;
    }
    return raiz;
}

O custo é proporcional ao número de nós no caminho percorrido, ou seja, O(h), em que h é a altura da árvore (OpenDSA Project Contributors, 2023). Em uma árvore razoavelmente equilibrada, h é da ordem de log n; em uma árvore degenerada, que lembra uma lista, h é da ordem de n. Voltaremos a esse ponto nas limitações.

Modificação: inserção

Inserir uma chave k exige, primeiro, localizar a posição correta, com a mesma descida da busca. Se a chave já existe, nada é feito (pela nossa simplificação). Se a descida termina em nullptr, criamos ali um novo nó, que se torna folha. Toda inserção, portanto, acrescenta uma folha e nunca reorganiza nós existentes.

Figura 3. Inserção da chave 5: o novo nó ocupa o filho esquerdo de 6 (em destaque).

flowchart TD
    A["8"] -->|esq| B["4"]
    A -->|dir| C["12"]
    B -->|esq| D["2"]
    B -->|dir| E["6"]
    E -->|esq| H["5"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]
    classDef novo fill:#bbf7d0,stroke:#15803d,stroke-width:2px
    class H novo

A implementação recursiva é concisa: a função devolve a raiz da subárvore já atualizada, e o chamador reatribui o ponteiro. Quando a recursão chega a nullptr, devolve o novo nó, que é ligado ao pai pela atribuição raiz->esq = ... ou raiz->dir = .... O parâmetro inseriu informa se houve inserção ou se a chave era duplicada.

No* inserir(No* raiz, int chave, bool& inseriu) {
    if (raiz == nullptr) {
        inseriu = true;
        return new No(chave);
    }
    if (chave < raiz->chave) {
        raiz->esq = inserir(raiz->esq, chave, inseriu);
    } else if (chave > raiz->chave) {
        raiz->dir = inserir(raiz->dir, chave, inseriu);
    }
    return raiz;
}

O custo também é O(h). Um ponto crucial é que a forma da árvore depende da ordem de inserção. As chaves 8, 4, 12, 2, 6, 10, 14 produzem a Figura 1, mas a inserção em ordem crescente (2, 4, 6, 8, 10, 12, 14) produz uma cadeia de nós só com filhos à direita, de altura 6 (OpenDSA Project Contributors, 2023).

Modificação: remoção

A remoção é a operação mais delicada, pois retirar um nó pode deixar subárvores “órfãs”. Há três casos, conforme o número de filhos do nó que contém a chave (Cormen et al., 2022; OpenDSA Project Contributors, 2023). Em todos eles, a primeira etapa é localizar o nó por descida, como na busca.

Caso 1: nó sem filhos (folha)

Basta ligar o ponteiro do pai a nullptr. Removendo o 2 da árvore da Figura 3:

Figura 4. Remoção da folha 2.

flowchart TD
    A["8"] -->|esq| B["4"]
    A -->|dir| C["12"]
    B -->|dir| E["6"]
    E -->|esq| H["5"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]

Caso 2: nó com um filho

O filho único (com toda a sua subárvore) ocupa o lugar do nó removido: o pai passa a apontar diretamente para ele. A propriedade se mantém porque toda a subárvore já estava do mesmo lado correto em relação aos ancestrais. Removendo o 4, que na Figura 4 só tem o filho direito 6:

Figura 5. Remoção do nó 4, que tinha um único filho; a subárvore de 6 sobe (em destaque).

flowchart TD
    A["8"] -->|esq| E["6"]
    A -->|dir| C["12"]
    E -->|esq| H["5"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]
    classDef sobe fill:#bbf7d0,stroke:#15803d,stroke-width:2px
    class E,H sobe

Caso 3: nó com dois filhos

Aqui não há um único candidato a assumir o lugar do nó. A solução clássica usa o sucessor: a menor chave maior que a do nó, que está no nó mais à esquerda da subárvore direita (Cormen et al., 2022). O procedimento é:

  1. localizar o sucessor (descer uma vez à direita e depois sempre à esquerda);
  2. copiar a chave do sucessor para o nó que se quer remover;
  3. remover o nó do sucessor da subárvore direita. Como ele é o mais à esquerda, não tem filho esquerdo, e recai no caso 1 ou 2.

A cópia preserva a propriedade: o sucessor é maior que todas as chaves da subárvore esquerda e menor ou igual a todas as outras da direita. Simétrica é a variante que usa o predecessor (o nó mais à direita da subárvore esquerda). Para remover a raiz 8 da Figura 5, o sucessor é 10, o menor da subárvore de 12:

Figura 6. Antes da remoção da raiz 8: o nó a remover (laranja) e seu sucessor 10 (verde).

flowchart TD
    A["8"] -->|esq| E["6"]
    A -->|dir| C["12"]
    E -->|esq| H["5"]
    C -->|esq| F["10"]
    C -->|dir| G["14"]
    classDef alvo fill:#fed7aa,stroke:#c2410c,stroke-width:2px
    classDef sucessor fill:#bbf7d0,stroke:#15803d,stroke-width:2px
    class A alvo
    class F sucessor

Copiamos 10 para a raiz e removemos o nó 10 original da subárvore direita (uma folha, caso 1). O resultado é:

Figura 7. ABB final: a raiz passou a ser 10 e 12 ficou apenas com o filho direito 14.

flowchart TD
    A["10"] -->|esq| E["6"]
    A -->|dir| C["12"]
    E -->|esq| H["5"]
    C -->|dir| G["14"]

A função minimo desce pela esquerda até o último nó. Em remover, os casos 1 e 2 são tratados juntos: se um dos filhos for nullptr, devolvemos o outro (que será nullptr na folha), liberando o nó removido. O caso 3 copia a chave do sucessor e chama remover recursivamente na subárvore direita; o parâmetro auxiliar descarta o indicador dessa segunda chamada.

No* minimo(No* raiz) {
    while (raiz->esq != nullptr) {
        raiz = raiz->esq;
    }
    return raiz;
}

No* remover(No* raiz, int chave, bool& removeu) {
    if (raiz == nullptr) {
        return nullptr;
    }
    if (chave < raiz->chave) {
        raiz->esq = remover(raiz->esq, chave, removeu);
    } else if (chave > raiz->chave) {
        raiz->dir = remover(raiz->dir, chave, removeu);
    } else {
        removeu = true;
        if (raiz->esq == nullptr) {
            No* filho = raiz->dir;
            delete raiz;
            return filho;
        }
        if (raiz->dir == nullptr) {
            No* filho = raiz->esq;
            delete raiz;
            return filho;
        }
        No* sucessor = minimo(raiz->dir);
        raiz->chave = sucessor->chave;
        bool auxiliar = false;
        raiz->dir = remover(raiz->dir, sucessor->chave, auxiliar);
    }
    return raiz;
}

minimo exige árvore não vazia; em remover isso é garantido, pois só é chamado quando o nó tem filho direito. O custo da remoção é O(h): descemos até o nó e, no caso 3, mais um trecho até o sucessor, sem nunca ultrapassar a altura da árvore (OpenDSA Project Contributors, 2023).

Execução do exemplo completo

Para conferir as operações, as funções auxiliares abaixo percorrem a árvore em ordem (a saída deve ser sempre crescente) e liberam a memória.

void emOrdem(const No* raiz, std::vector<int>& saida) {
    if (raiz == nullptr) {
        return;
    }
    emOrdem(raiz->esq, saida);
    saida.push_back(raiz->chave);
    emOrdem(raiz->dir, saida);
}

void liberar(No* raiz) {
    if (raiz == nullptr) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    delete raiz;
}

void imprimir(const char* rotulo, const No* raiz) {
    std::vector<int> chaves;
    emOrdem(raiz, chaves);
    std::cout << rotulo << ":";
    for (int c : chaves) {
        std::cout << ' ' << c;
    }
    std::cout << '\n';
}

A função main reproduz a sequência das figuras: monta a Figura 1, busca 6 e 5, insere 5 (e tenta inserir 6 de novo), remove 2 (folha), 4 (um filho), 8 (dois filhos) e tenta remover 99, ausente.

int main() {
    No* raiz = nullptr;
    bool feito = false;
    for (int c : {8, 4, 12, 2, 6, 10, 14}) {
        raiz = inserir(raiz, c, feito);
    }
    imprimir("Árvore inicial", raiz);
    std::cout << "buscar(6): " << (buscar(raiz, 6) != nullptr ? "encontrada" : "ausente") << '\n';
    std::cout << "buscar(5): " << (buscar(raiz, 5) != nullptr ? "encontrada" : "ausente") << '\n';

    feito = false;
    raiz = inserir(raiz, 5, feito);
    std::cout << "inserir(5): " << (feito ? "inserida" : "duplicada") << '\n';
    feito = false;
    raiz = inserir(raiz, 6, feito);
    std::cout << "inserir(6): " << (feito ? "inserida" : "duplicada") << '\n';
    imprimir("Após inserções", raiz);

    for (int c : {2, 4, 8, 99}) {
        feito = false;
        raiz = remover(raiz, c, feito);
        std::cout << "remover(" << c << "): " << (feito ? "removida" : "ausente") << '\n';
        imprimir("Em ordem", raiz);
    }
    std::cout << "Raiz final: " << raiz->chave << '\n';
    liberar(raiz);
    return 0;
}

Reunindo os blocos cpp do artigo, na ordem em que aparecem, em um único arquivo e compilando com g++ -std=c++17, a saída é:

Árvore inicial: 2 4 6 8 10 12 14
buscar(6): encontrada
buscar(5): ausente
inserir(5): inserida
inserir(6): duplicada
Após inserções: 2 4 5 6 8 10 12 14
remover(2): removida
Em ordem: 4 5 6 8 10 12 14
remover(4): removida
Em ordem: 5 6 8 10 12 14
remover(8): removida
Em ordem: 5 6 10 12 14
remover(99): ausente
Em ordem: 5 6 10 12 14
Raiz final: 10

A cada operação, o percurso em ordem continua crescente, o que é consistente com a preservação da propriedade da ABB. A raiz final, 10, confirma a substituição pelo sucessor e coincide com a Figura 7.

Custos e limitações

Busca, inserção e remoção custam O(h). Se a árvore for equilibrada, h é da ordem de log n, e as operações custam Θ(log n) em média; se não for, uma única operação pode custar Θ(n). Inserir n chaves em ordem aleatória custa cerca de Θ(n log n) no total, enquanto inseri-las em ordem crescente custa Θ(n²), pois cada inserção percorre toda a cadeia (OpenDSA Project Contributors, 2023). Isto motiva árvores com balanceamento automático, como as AVL, que reorganizam a estrutura após inserções e remoções e ficam fora do escopo deste artigo.

Outras limitações da implementação apresentada:

  • a recursão usa espaço de pilha proporcional a h, o que pode estourar a pilha em árvores muito degeneradas;
  • a remoção por cópia da chave serve para inteiros; com objetos grandes, ou quando outros ponteiros referenciam o nó, é preferível religar o nó sucessor em vez de copiar;
  • usar sempre o sucessor (e nunca o predecessor) pode, em sequências longas de remoções, deixar a árvore desbalanceada para um lado. Alternar entre os dois é uma alternativa prática, não uma garantia.

Síntese

Uma ABB mantém, em cada nó, as chaves menores à esquerda e as maiores à direita; o percurso em ordem entrega as chaves ordenadas. A busca desce por um único caminho; a inserção acrescenta uma folha na posição em que a busca falharia; a remoção distingue folha, nó com um filho e nó com dois filhos, neste último caso substituindo a chave pelo sucessor. As três operações custam O(h), e a altura depende da ordem das operações, o que justifica o estudo de árvores balanceadas.

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to algorithms. 4. ed. Cambridge: MIT Press, 2022.

OPENDSA PROJECT CONTRIBUTORS. Binary search trees. OpenDSA Stand-alone Modules, 2023. Disponível em: https://opendsa-server.cs.vt.edu/ODSA/StandaloneModules/20231208151338/html/BST.html. Acesso em: 30 out. 2026.

Atividade de fixação

Partindo da ABB da Figura 7 (raiz 10; 6 com filho esquerdo 5; 12 com filho direito 14), insira as chaves 11 e 13, nessa ordem, e desenhe a árvore. Em seguida, remova a raiz 10 usando o sucessor e desenhe o resultado, indicando qual dos três casos de remoção se aplica ao nó do sucessor. Por fim, explique por que a inserção de 1, 2, 3, 4 em uma ABB vazia produz uma árvore de altura 3 e o que isso implica para o custo da busca.