Guia Completo de Estruturas de Dados e Algoritmos

O que é Recursividade

Uma rotina ou função é recursiva quando ela chama a si mesma, seja de forma direta ou indireta.

long fat_recursivo(int numero) {
  if (numero == 0) return 1;
  else if (numero >= 2) return numero * fat_recursivo(numero - 1);
  else return numero;
}

• Direta: Quando a função chama a si mesma.
• Indireta: Quando "P" chama "Q", que chama "R", até que "P" seja novamente invocada.

Vantagens e Desvantagens

Desvantagem: Cada chamada recursiva implica maior consumo de tempo e espaço, pois as variáveis locais são recriadas a cada chamada.

Vantagem: Se bem utilizada, torna o algoritmo mais elegante, conciso e simples.

Estruturas de Dados: Árvores

Uma árvore é um tipo abstrato de dados que armazena elementos de maneira hierárquica.

• Nodo externo (folha): Não possui filhos.
• Nodo interno: Possui um ou mais filhos.
• Profundidade: Número de ancestrais de um nodo (excluindo ele mesmo). A raiz tem profundidade 0.
• Altura: Comprimento do caminho mais longo até um nodo folha.

Percursos em Árvores

• Prefixado: O nodo é visitado antes de seus descendentes.
• Pós-fixado: O nodo é visitado após seus descendentes.

Árvores Binárias

Uma árvore binária é uma árvore ordenada na qual todo nodo tem, no máximo, dois filhos.

Caminhamento Interfixado

Percorre da esquerda para a direita.

Árvore Binária de Busca

Regras de busca:

• Se for menor, segue para a esquerda.
• Se for maior, segue para a direita.
• Se for igual, a pesquisa terminou com sucesso.
• Se encontrar um nodo externo (vazio), a pesquisa terminou sem sucesso.

Algoritmos de Ordenação

Bubble Sort

Algoritmo simples de troca. Pior caso: O(n²), Melhor caso: O(n).

Quick Sort

Algoritmo eficiente de divisão e conquista. Complexidade: Ω(n log n) no melhor e médio caso; O(n²) no pior caso.

Grafos

Compostos por vértices e arestas (podem ser dirigidos, não dirigidos ou mistos).

• Grau: Número de arestas ligadas a um vértice.
• Fonte: Vértice com grau de entrada 0.
• Sumidouro: Vértice com grau de saída 0.