Conteúdo da Aula

Primeiro horário: Fundamentos Teóricos

• Conceitos básicos de árvores
• Estrutura do nó
• Inserção básica

Conteúdo da Aula (cont.)

Segundo horário: Busca e Complexidade

• Implementação da busca
• Análise de complexidade
• BST vs outras estruturas

Conteúdo da Aula (cont.)

Terceiro horário: Percursos (Traversals)

• Em ordem (in-order)
• Pré-ordem (pre-order)
• Pós-ordem (post-order)

Conteúdo da Aula (cont.)

Quarto horário: Operações Avançadas

• Remoção de nós
• Aplicações práticas
• Exercícios

Definição de uma Árvore Binária

Uma árvore binária é uma estrutura de dados hierárquica onde:

• Cada nó possui no máximo dois filhos
• Os filhos são chamados de esquerda e direita
• Existe um nó especial chamado raiz

Características de uma Árvore Binária

• Estrutura hierárquica
• Acesso eficiente aos dados
• Organização natural dos elementos
• Base para algoritmos avançados

Terminologia Importante

        50      ← Raiz
       /  \
      30   70    ← Nós internos
     / \   / \
    20 40 60 80  ← Folhas

Termos Fundamentais

• Raiz: Nó no topo da árvore
• Folha: Nó sem filhos
• Nó interno: Nó com pelo menos um filho
• Subárvore: Árvore formada por um nó e seus descendentes
• Altura: Maior distância da raiz até uma folha
• Nível: Distância de um nó até a raiz

Árvore Binária de Busca (BST)

Propriedade Fundamental

Para qualquer nó da árvore:

• Todos os valores da subárvore esquerda são menores
• Todos os valores da subárvore direita são maiores

        50
       /  \
      30   70     ← 30 < 50 < 70
     / \   / \
    20 40 60 80   ← 20 < 30, 40 > 30, 60 < 70, 80 > 70

Vantagens

• Busca eficiente
• Inserção ordenada
• Operações em no caso médio

Estrutura do Nó em C

// Definição da estrutura do nó
typedef struct No {
    int dado;               // Valor armazenado
    struct No *esquerda;    // Ponteiro para filho esquerdo
    struct No *direita;     // Ponteiro para filho direito
} No;

Criação do Nó em C

// Função para criar um novo nó
No *criarNo(int valor) {
    No *novoNo = (No*)malloc(sizeof(No));
    if (novoNo == NULL) {
        printf("Erro: Falha na alocação de memória!\n");
        exit(1);
    }
    novoNo->dado = valor;
    novoNo->esquerda = NULL;
    novoNo->direita = NULL;
    return novoNo;
}

Inserção em BST

Algoritmo

1. Se a árvore estiver vazia, criar novo nó como raiz
2. Comparar valor com nó atual:
   • Se menor → ir para esquerda
   • Se maior → ir para direita
3. Repetir até encontrar posição vazia
4. Inserir novo nó

Inserção em BST em C

No *inserir(No *raiz, int valor) {
    // Caso base: posição encontrada
    if (raiz == NULL) {
        return criarNo(valor);
    }
    
    // Escolher direção baseada no valor
    if (valor < raiz->dado) {
        raiz->esquerda = inserir(raiz->esquerda, valor);
    } else if (valor > raiz->dado) {
        raiz->direita = inserir(raiz->direita, valor);
    }
    
    return raiz;
}

Exemplo Prático de Inserção

Inserindo: 50, 30, 70, 20, 40

Passo 1: Inserir 50         Passo 2: Inserir 30       Passo 3: Inserir 70
    50                          50                          50
                               /                           /  \
                              30                          30   70

Passo 4: Inserir 20         Passo 5: Inserir 40
    50                          50
   /  \                        /  \
  30   70                     30   70
 /                           /  \
20                          20  40

Demonstração Prática

Vamos implementar juntos!

1. Criar a estrutura do nó
2. Implementar a função de criar nó
3. Implementar inserção recursiva
4. Testar com alguns valores

Exercício de fixação do primeiro horário

Problema

Dada a sequência de inserção: [25, 15, 35, 10, 20, 30, 40]

Desenhe a BST resultante e identifique:

1. Qual é a raiz?
2. Quantas folhas existem?
3. Qual a altura da árvore?
4. Quais nós estão no nível 2?

Tempo: 10 minutos / Trabalho em duplas

Implementando a Busca

Algoritmo de Busca

1. Começar pela raiz
2. Comparar valor procurado com nó atual:
   • Se igual → encontrado!
   • Se menor → buscar na esquerda
   • Se maior → buscar na direita
3. Repetir até encontrar ou chegar em nó NULL

Implementação desse algoritmo em C

bool buscar(No *raiz, int valor) {
    // Caso base: árvore vazia ou valor não encontrado
    if (raiz == NULL) {
        return false;
    }
    // Valor encontrado
    if (raiz->dado == valor) {
        return true;
    }
    // Escolher direção da busca
    if (valor < raiz->dado) {
        return buscar(raiz->esquerda, valor);
    } else {
        return buscar(raiz->direita, valor);
    }
}

Análise de Complexidade

Caso Médio (Árvore Balanceada)

        50
       /  \
      30   70    ← Altura: log₂(n)
     / \   / \
    20 40 60 80

• Inserção:
• Busca:
• Espaço:

Pior Caso (Árvore Degenerada)

50
 \
  60    ← Altura: n
   \
    70
     \
      80

• Inserção:
• Busca:

BST vs Outras Estruturas

Vantagens da BST

• Busca eficiente sem necessidade de ordenação prévia
• Inserção dinâmica mantendo ordem
• Flexibilidade para crescimento

Exemplo de Busca

Buscar o valor 40 na árvore:

        50     ← 40 < 50, vai para esquerda
       /  \
      30   70   ← 40 > 30, vai para direita
     / \   / \
    20 40 60 80 ← 40 = 40, ENCONTRADO!

• Passos percorridos: 50 → 30 → 40
• Comparações necessárias: 3
• Em uma lista: seriam necessárias 4 comparações

Calculando Complexidade

Para uma BST com n elementos balanceada:

Demonstração de Busca

// Testando diferentes valores
int valorBusca[] = {40, 25, 80, 100};

for (int i = 0; i < 4; i++) {
    if (buscar(raiz, valorBusca[i])) {
        printf("Valor %d: ENCONTRADO\n", valorBusca[i]);
    } else {
        printf("Valor %d: NÃO ENCONTRADO\n", valorBusca[i]);
    }
}

Exercício de fixação do segundo horário

Problema: Análise de Busca

Para a BST abaixo, determine quantas comparações são necessárias para:

        15
       /  \
      10   20
     / \     \
    5  12    25

Analise a solução para

Buscar os valores:

1. 5 → Comparações: ____
2. 20 → Comparações: ____
3. 12 → Comparações: ____
4. 25 → Comparações: ____

Tempo: 8 minutos

Percursos são definidos como:

Algoritmos para visitar todos os nós de uma árvore de forma sistemática.

Por que são importantes?

• Processar todos os dados
• Buscar informações específicas
• Copiar ou serializar árvores
• Liberar memória adequadamente
• Avaliar expressões matemáticas

Tipos Principais

1. Em ordem (In-order)
2. Pré-ordem (Pre-order)
3. Pós-ordem (Post-order)

Em Ordem (In-Order)

Algoritmo: Esquerda → Raiz → Direita

void percursoEmOrdem(No *raiz) {
    if (raiz != NULL) {
        percursoEmOrdem(raiz->esquerda);     // Esquerda
        printf("%d ", raiz->dado);           // Raiz
        percursoEmOrdem(raiz->direita);      // Direita
    }
}

Exemplo:

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Resultado: 20 30 40 50 60 70 80

Em uma BST, produz valores em ordem crescente!

Pré-Ordem (Pre-Order)

Algoritmo: Raiz → Esquerda → Direita

void percursoPreOrdem(No *raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->dado);           // Raiz
        percursoPreOrdem(raiz->esquerda);    // Esquerda
        percursoPreOrdem(raiz->direita);     // Direita
    }
}

Exemplo:

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Resultado: 50 30 20 40 70 60 80

Útil para copiar árvores e expressões prefixas!

Pós-Ordem (Post-Order)

Algoritmo: Esquerda → Direita → Raiz

void percursoPosOrdem(No *raiz) {
    if (raiz != NULL) {
        percursoPosOrdem(raiz->esquerda);    // Esquerda
        percursoPosOrdem(raiz->direita);     // Direita
        printf("%d ", raiz->dado);           // Raiz
    }
}

Exemplo:

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Resultado: 20 40 30 60 80 70 50

Útil para liberar memória e expressões sufixas!

Comparando os Percursos

        50
       /  \
      30   70
     / \   / \
    20 40 60 80

Dica: A posição da "Raiz" no nome indica quando ela é visitada!

Visualizando os Percursos

Em Ordem (Left → Root → Right)

1. Vai até o nó mais à esquerda (20)
2. Visita o nó (20)
3. Sobe e visita o pai (30)
4. Vai para direita e visita (40)
5. Continue o padrão...

Visualizando os Percursos (cont.)

Pré-Ordem (Root → Left → Right)

1. Visita a raiz imediatamente (50)
2. Desce para esquerda (30)
3. Continue recursivamente...

Visualizando os Percursos (cont.)

Pós-Ordem (Left → Right → Root)

1. Vai até as folhas primeiro
2. Visita filhos antes dos pais
3. Raiz é sempre a última

Aplicações Práticas

Em Ordem

• Imprimir BST ordenada
• Validar se árvore é BST
• Converter BST para array ordenado

Aplicações Práticas (cont.)

Pré-Ordem

• Serializar árvore (salvar em arquivo)
• Copiar estrutura da árvore
• Avaliar expressões prefixas (+ 2 3)

Aplicações Práticas (cont.)

Pós-Ordem

• Liberar memória (filhos antes dos pais)
• Calcular tamanho de diretórios
• Avaliar expressões sufixas (2 3 +)

Demonstração dos Percursos

Vamos executar todos os percursos!

printf("Em Ordem:    ");
percursoEmOrdem(raiz);

printf("\nPré-Ordem:   ");  
percursoPreOrdem(raiz);

printf("\nPós-Ordem:   ");
percursoPosOrdem(raiz);

Observe atentamente:

• Como os valores aparecem em cada percurso
• A ordem dos nós visitados
• A natureza recursiva dos algoritmos

Exercício de fixação do terceiro horário

Para a árvore abaixo, determine a sequência de cada percurso:

        25
       /  \
      15   35
     / \   / \
    10 20 30 40

Complete:

1. Em Ordem: __ __ __ __ __ __ __
2. Pré-Ordem: __ __ __ __ __ __ __
3. Pós-Ordem: __ __ __ __ __ __ __

Tempo: 10 minutos

Trabalho individual, depois discussão em grupo

Remoção em BST

Complexidade da Remoção

A remoção é a operação mais complexa em BST pois precisamos manter a propriedade de ordenação.

Três Casos Possíveis:

1. Nó folha (sem filhos) - Simples
2. Nó com um filho - Moderado
3. Nó com dois filhos - Complexo

Cada caso requer estratégia diferente!

Caso 1: Remover Nó Folha

Estratégia: simplesmente remover

// Exemplo: Remover 20
        50              50
       /  \            /  \  
      30   70   →     30   70
     / \   / \         \   / \
    20 40 60 80        40 60 80

if (raiz->esquerda == NULL && raiz->direita == NULL) {
    free(raiz);
    return NULL;
}

Simples: apenas liberar o nó!

Caso 2: Nó com Um Filho

Estratégia: conectar filho diretamente ao avô

// Exemplo: Remover 30 (que tem apenas filho direito 40)
        50              50
       /  \            /  \
      30   70   →     40   70  
       \   / \             / \
        40 60 80          60 80

Implementação desse algoritmo em C

else if (raiz->esquerda == NULL) {
    No *temp = raiz->direita;
    free(raiz);
    return temp;
} else if (raiz->direita == NULL) {
    No *temp = raiz->esquerda;
    free(raiz);
    return temp;
}

Caso 3: Nó com Dois Filhos

Estratégia: substituir por sucessor

1. Encontrar sucessor (menor valor da subárvore direita)
2. Copiar valor do sucessor para o nó atual
3. Remover o sucessor (que terá no máximo 1 filho)

// Exemplo: Remover 50
        50              60
       /  \            /  \
      30   70   →     30   70
     / \   / \       / \    \
    20 40 60 80     20 40   80

Sucessor: sempre mantém propriedade da BST!

Implementação da Remoção

No *remover(No *raiz, int valor) {
    if (raiz == NULL) return raiz;
    if (valor < raiz->dado) {
        raiz->esquerda = remover(raiz->esquerda, valor);
    } else if (valor > raiz->dado) {
        raiz->direita = remover(raiz->direita, valor);
    } else {
        // Nó encontrado - aplicar um dos três casos
        // Caso 1: Nó folha
        if (raiz->esquerda == NULL && raiz->direita == NULL) {
            free(raiz);
            return NULL;
        }
        // Caso 2: Um filho
        else if (raiz->esquerda == NULL) {
            No *temp = raiz->direita;
            free(raiz);
            return temp;
        } else if (raiz->direita == NULL) {
            No *temp = raiz->esquerda;
            free(raiz);
            return temp;
        }
        // Caso 3: Dois filhos
        else {
            No *sucessor = encontrarMinimo(raiz->direita);
            raiz->dado = sucessor->dado;
            raiz->direita = remover(raiz->direita, sucessor->dado);
        }
    }
    return raiz;
}

Aplicações Práticas de BST

Outras Operações Úteis

Calcular altura da árvore

int altura(No *raiz) {
    if (raiz == NULL) return -1;
    
    int altEsq = altura(raiz->esquerda);
    int altDir = altura(raiz->direita);
    
    return 1 + (altEsq > altDir ? altEsq : altDir);
}

Outras Operações Úteis (cont.)

Contar Nós

int contarNos(No *raiz) {
    if (raiz == NULL) return 0;
    return 1 + contarNos(raiz->esquerda) + contarNos(raiz->direita);
}

Outras Operações Úteis (cont.)

Liberar Memória (Pós-ordem!)

void liberarArvore(No *raiz) {
    if (raiz != NULL) {
        liberarArvore(raiz->esquerda);
        liberarArvore(raiz->direita);
        free(raiz);  // Liberar depois dos filhos!
    }
}

Exemplo Completo de Uso

int main() {
    No *raiz = NULL;
    // Inserções
    int valores[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) {
        raiz = inserir(raiz, valores[i]);
    }
    // Informações
    printf("Altura: %d\n", altura(raiz));
    printf("Total de nós: %d\n", contarNos(raiz));
    // Percursos
    printf("Em ordem: ");
    percursoEmOrdem(raiz);
    // Buscas
    printf("\nBuscar 40: %s\n", buscar(raiz, 40) ? "Encontrado" : "Não encontrado");
    // Remoção
    raiz = remover(raiz, 30);
    // Limpeza
    liberarArvore(raiz);
    return 0;
}

Comparação Final: BST vs Outras Estruturas

Critério	Array	Lista Ligada	Hash Table	BST
Busca	*		**
Inserção			**
Ordenação	Prévia			Automática
Memória	Compacta	Extra	Extra	Moderada
Range Query				Eficiente

*Array ordenado | **Caso médio

BST é ideal quando você precisa de dados ordenados com operações eficientes!

Evolução: Árvores Balanceadas

Problema da BST Simples

• Pode degenerar em lista ()
• Depende da ordem de inserção

Soluções Avançadas

• AVL Tree: Balanceamento automático
• Red-Black Tree: Usado em bibliotecas padrão
• B-Tree: Para sistemas de arquivos
• Splay Tree: Auto-otimização por uso

Exercício Desafio

Implemente um programa que:

1. Crie uma BST com valores: [15, 10, 20, 8, 12, 25, 6, 11, 13, 22, 27]
2. Realize os três percursos e mostre os resultados
3. Busque os valores 11 e 20, contando comparações
4. Remova o nó 10 (que tem dois filhos)
5. Mostre o percurso em ordem após a remoção
6. Calcule altura e total de nós da árvore final

Tempo: para casa / Grupos de 3-4 pessoas

Resumo de hoje

O que aprendemos:

Perguntas e Discussão