Árvores Binárias de Pesquisa (BST)

1. Introdução às Árvores

Até agora, nossas estruturas eram lineares (um após o outro). Agora, entramos no mundo hierárquico. Uma Árvore é uma coleção de nós, onde existe um nó especial chamado Raiz e os demais são divididos em subconjuntos disjuntos (subárvores).

As BSTs (Binary Search Trees) combinam a flexibilidade de inserção das listas encadeadas com a eficiência de busca dos vetores ordenados.

2. Definição Formal de BST

Uma árvore binária é uma Árvore Binária de Pesquisa se, e somente se, para qualquer nó u: 1. Todas as chaves na subárvore Esquerda de u são menores que u.chave. 2. Todas as chaves na subárvore Direita de u são maiores que u.chave. 3. As subárvores esquerda e direita também são BSTs.

Essa propriedade garante que, se percorrermos a árvore em ordem simétrica (In-Order), visitaremos os elementos de forma crescente.

3. Implementação em Java

Vamos definir a classe do Nó e a estrutura da BST.

public class BST {
    
    private class Node {
        int key;
        Node left, right;
        
        public Node(int item) {
            key = item;
            left = right = null;
        }
    }
    
    private Node root;
    
    public BST() {
        root = null;
    }
    
    // Métodos públicos (API)
    public void insert(int key) { root = insertRec(root, key); }
    public boolean search(int key) { return searchRec(root, key); }
    public void delete(int key) { root = deleteRec(root, key); }
}

3.1. Inserção

A inserção sempre ocorre nas folhas (exceto se a chave já existir). Descemos pela árvore comparando: se é menor, vai pra esquerda; se maior, direita. Ao atingir null, inserimos.

private Node insertRec(Node root, int key) {
    // Caso Base: árvore vazia ou chegou na folha
    if (root == null) {
        return new Node(key);
    }
    
    // Case Recursivo: navegação
    if (key < root.key)
        root.left = insertRec(root.left, key);
    else if (key > root.key)
        root.right = insertRec(root.right, key);
    
    // Retorna o nó (inalterado) para manter o encadeamento
    return root; 
}

3.2. Busca

A complexidade é proporcional à altura da árvore (\(h\)). - Melhor caso (balanceada): \(O(\log N)\). - Pior caso (degenerada em lista): \(O(N)\).

private boolean searchRec(Node root, int key) {
    if (root == null) return false;
    if (root.key == key) return true;
    
    if (key < root.key)
        return searchRec(root.left, key);
    else
        return searchRec(root.right, key);
}

4. Remoção: O Grande Desafio

Remover é mais complexo pois não podemos quebrar a estrutura da árvore. Existem 3 casos:

  1. Nó Folha: Basta setar o ponteiro do pai para null.
  2. Nó com 1 Filho: O pai aponta direto para o filho único (pula o nó removido).
  3. Nó com 2 Filhos: Não podemos remover simplesmente. Estratégia:
    • Encontre o Sucessor (o menor valor da subárvore direita).
    • Copie o valor do sucessor para o nó atual.
    • Remova o sucessor (que cairá no caso 1 ou 2, pois o menor da direita nunca tem filho esquerdo!).
private Node deleteRec(Node root, int key) {
    if (root == null) return root;

    // 1. Procurar o nó
    if (key < root.key)
        root.left = deleteRec(root.left, key);
    else if (key > root.key)
        root.right = deleteRec(root.right, key);
    else {
        // Encontrou o nó a ser removido
        
        // Caso 1 e 2: 0 ou 1 filho
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // Caso 3: 2 filhos
        // Pega o menor valor da subárvore direita (sucessor)
        root.key = minValue(root.right);
        
        // Remove o sucessor recursivamente
        root.right = deleteRec(root.right, root.key);
    }
    return root;
}

private int minValue(Node root) {
    int min = root.key;
    while (root.left != null) {
        min = root.left.key;
        root = root.left;
    }
    return min;
}

5. Percursos (Traversals)

Maneiras sistemáticas de visitar todos os nós.

BFS (Breadth-First Search) - Nível a Nível

Usa uma Fila. Visita raiz, depois filhos da raiz, depois netos…

public void levelOrder() {
    if (root == null) return;
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        Node temp = queue.poll();
        System.out.print(temp.key + " ");
        
        if (temp.left != null) queue.add(temp.left);
        if (temp.right != null) queue.add(temp.right);
    }
}

6. O Problema do Balanceamento

Se inserirmos os números na ordem 1, 2, 3, 4, 5, a BST vira uma “escada” para a direita (lista encadeada). A altura \(h\) vira \(N\), e a busca \(O(N)\). Para garantir eficiência \(O(\log N)\), a árvore precisa estar Balanceada (altura próxima de \(\log_2 N\)). Isso nos leva ao próximo tópico: Árvores AVL.

Back to top