Aula 13 - Árvores Binárias e Árvores de Busca Binária (BST) 🧱

📑 1. Fundamentos Teóricos & Análise Estrutural

Estrutura não-linear hierárquica, raiz, filhos, folhas, altura e profundidade. Inserção, busca e remoção em BST. Travessias Em-Ordem, Pré-Ordem e Pós-Ordem. O domínio desta estrutura de dados é primordial para o desenvolvimento de software escalável, onde o consumo de ciclos de CPU e a alocação de memória RAM na heap determinam a viabilidade operacional do sistema.

📐 Representação Abstrata & Mapeamento em Memória

graph LR
    A["Entrada de Dados"] --> B["Árvores Binárias e Árvores de Busca Binária (BST)"]
    B --> C["Operação / Manipulação de Ponteiros"]
    C --> D["Resultado / Complexidade Assintótica"]

    style A fill:#e3f2fd,stroke:#1565c0
    style B fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style C fill:#e8f5e9,stroke:#2e7d32
    style D fill:#f3e5f5,stroke:#7b1fa2

🔍 Pilares e Propriedades Algorítmicas

Nesta unidade, exploramos formalmente: - Propriedade da BST: Fundamento teórico indispensável para a correta aplicação computacional. - Busca O(h): Fundamento teórico indispensável para a correta aplicação computacional. - Travessia Em-Ordem (Ordenada): Fundamento teórico indispensável para a correta aplicação computacional. - Pré-Ordem e Pós-Ordem: Fundamento teórico indispensável para a correta aplicação computacional. - Degeneração em Lista: Fundamento teórico indispensável para a correta aplicação computacional.

🛠️ 2. Implementação Técnica em Linguagem C

Abaixo está o código de referência estruturado seguindo os padrões de boas práticas da linguagem C (ANSI C / C99), com gerenciamento dinâmico de memória e verificação de ponteiros nulos:

// Árvore de Busca Binária (BST)
typedef struct NoBST {
    int chave;
    struct NoBST *esq, *dir;
} NoBST;

NoBST* bst_inserir(NoBST* raiz, int chave) {
    if (raiz == NULL) {
        NoBST* n = (NoBST*) malloc(sizeof(NoBST));
        n->chave = chave; n->esq = n->dir = NULL;
        return n;
    }
    if (chave < raiz->chave) raiz->esq = bst_inserir(raiz->esq, chave);
    else if (chave > raiz->chave) raiz->dir = bst_inserir(raiz->dir, chave);
    return raiz;
}

void bst_em_ordem(NoBST* raiz) {
    if (raiz != NULL) {
        bst_em_ordem(raiz->esq);
        printf("%d ", raiz->chave);
        bst_em_ordem(raiz->dir);
    }
}

💡 Análise de Eficiência e Complexidade

1. Complexidade Temporal: A implementação prioriza caminhos de execução diretos para atingir o menor custo assintótico possível.
2. Gerenciamento de Memória: Toda alocação realizada na heap deve possuir uma rotina correspondente de liberação para assegurar vazamento zero de memória (zero memory leaks).
3. Casos de Borda: Tratamento rigoroso de listas vazias, ponteiros nulos (NULL) e estouros de capacidade.

🎯 3. Próximos Passos & Sequência Didática