Visão Geral das Operações

As Árvores Binárias de Busca (BST) são estruturas fundamentais para a organização de dados que permitem operações eficientes de busca, inserção e remoção. Neste estudo, exploramos as seguintes funcionalidades:

• Construção de uma árvore com inserção de 24 valores aleatórios.
• Implementação dos algoritmos de travessia: Pré-ordem, Em-ordem e Pós-ordem.
• Busca de elementos específicos na estrutura.
• Cálculo de métricas quantitativas: total de nós e número de folhas.
• Análise de profundidade: soma das profundidades das folhas, profundidade média e altura máxima (profundidade da folha mais distante).

Estrutura do Nó

O componente básico da árvore armazena o valor inteiro e as referências para os subnós esquerdo e direito.

public class NodoBST {
    int dado;
    NodoBST esquerdo, direito;

    public NodoBST(int valor) {
        this.dado = valor;
        this.esquerdo = null;
        this.direito = null;
    }

    public NodoBST(int valor, NodoBST esq, NodoBST dir) {
        this.dado = valor;
        this.esquerdo = esq;
        this.direito = dir;
    }
}

Lógica da Árvore Binária de Busca

Abaixo, a implementação da classe principal que gerencia a lógica de inserção, travessia e estatísticas da árvore.

public class ArvoreBinaria {
    private NodoBST raiz;

    public void inserir(int v) {
        raiz = inserirRecursivo(v, raiz);
    }

    private NodoBST inserirRecursivo(int v, NodoBST atual) {
        if (atual == null) {
            return new NodoBST(v);
        }
        if (v < atual.dado) {
            atual.esquerdo = inserirRecursivo(v, atual.esquerdo);
        } else {
            atual.direito = inserirRecursivo(v, atual.direito);
        }
        return atual;
    }

    public void exibirPreOrdem(NodoBST n) {
        if (n != null) {
            System.out.print(n.dado + " ");
            exibirPreOrdem(n.esquerdo);
            exibirPreOrdem(n.direito);
        }
    }

    public void exibirEmOrdem(NodoBST n) {
        if (n != null) {
            exibirEmOrdem(n.esquerdo);
            System.out.print(n.dado + " ");
            exibirEmOrdem(n.direito);
        }
    }

    public void exibirPosOrdem(NodoBST n) {
        if (n != null) {
            exibirPosOrdem(n.esquerdo);
            exibirPosOrdem(n.direito);
            System.out.print(n.dado + " ");
        }
    }

    public static int totalNos(NodoBST n) {
        return (n == null) ? 0 : 1 + totalNos(n.esquerdo) + totalNos(n.direito);
    }

    public static int contarFolhas(NodoBST n) {
        if (n == null) return 0;
        if (n.esquerdo == null && n.direito == null) return 1;
        return contarFolhas(n.esquerdo) + contarFolhas(n.direito);
    }

    public static boolean existe(NodoBST n, int alvo) {
        NodoBST cursor = n;
        while (cursor != null) {
            if (alvo == cursor.dado) return true;
            cursor = (alvo < cursor.dado) ? cursor.esquerdo : cursor.direito;
        }
        return false;
    }

    public static int somaProfundidadeFolhas(NodoBST n, int nivelAtual) {
        if (n == null) return 0;
        if (n.esquerdo == null && n.direito == null) return nivelAtual;
        return somaProfundidadeFolhas(n.esquerdo, nivelAtual + 1) + 
               somaProfundidadeFolhas(n.direito, nivelAtual + 1);
    }

    public static int profundidadeMaxima(NodoBST n, int nivelAtual) {
        if (n == null) return 0;
        if (n.esquerdo == null && n.direito == null) return nivelAtual;
        return Math.max(profundidadeMaxima(n.esquerdo, nivelAtual + 1), 
                        profundidadeMaxima(n.direito, nivelAtual + 1));
    }

    public NodoBST getRaiz() { return raiz; }
}

Execução e Testes de Balanceamento

O programa principle gera dados aleatórios para observar como a árvore se comporta sem mecanismos de auto-balanceamento.

import java.util.Random;

public class TesteBST {
    public static void main(String[] args) {
        ArvoreBinaria bst = new ArvoreBinaria();
        Random gerador = new Random();
        int limite = 24;

        for (int i = 0; i < limite; i++) {
            bst.inserir(gerador.nextInt(limite) + 1);
        }

        System.out.print("Pré-ordem: ");
        bst.exibirPreOrdem(bst.getRaiz());
        System.out.println("\nEm-ordem: ");
        bst.exibirEmOrdem(bst.getRaiz());
        
        int somaDep = ArvoreBinaria.somaProfundidadeFolhas(bst.getRaiz(), 0);
        int qtdFolhas = ArvoreBinaria.contarFolhas(bst.getRaiz());

        System.out.println("\n--- Estatísticas ---");
        System.out.println("Existe o valor " + limite + "? " + ArvoreBinaria.existe(bst.getRaiz(), limite));
        System.out.println("Total de nós: " + ArvoreBinaria.totalNos(bst.getRaiz()));
        System.out.println("Quantidade de folhas: " + qtdFolhas);
        System.out.println("Profundidade média das folhas: " + (double) somaDep / qtdFolhas);
        System.out.println("Altura da árvore (Max Dep): " + ArvoreBinaria.profundidadeMaxima(bst.getRaiz(), 0));
    }
}

Relatório Técnico de Desempenho

Embora os testes iniciais tenham sido realizados com 24 elementos para facilitar a visualização das travessias, simulações em larga escala (N=1024) revelam o comportamento assintótico da BST simples. Em dados distribuídos aleatoriamente, a profundidade média das folhas tende a ser cerca de 30% a 40% superior à de uma árvore binária completa. Por exemplo, enquanto uma árvore perfeitamente equilibrada teria profundidade próxima de 9 para 1024 nós, uma BST comum apresenta média em torno de 12 e máxima perto de 20.

Em termos de complexidade de tempo, a BST opera em média em O(log N). Contudo, em cenários de pior caso (dados inseridos de forma sequencial), a estrutura degenera em uma lista ligada, resultando em O(N). Para garantir a eficiência em sistemas críticos, recomenda-se a evolução para estruturas auto-balanceadas, como Árvores AVL ou Red-Black, que mantêm a altura controlada e asseguram o tempo logarítmico para todas as operações principais.