Árvores
Árvores em Algoritmos e Estruturas de Dados para Concursos
1. Conceitos Básicos
Árvores são estruturas de dados não lineares e hierárquicas, formadas por nós. Principais termos:
- Raiz (root): Nó superior (sem pai)
- Folha (leaf): Nó sem filhos
- Grau: Quantidade de subárvores de um nó
- Altura: Maior caminho da raiz até uma folha
2. Tipos de Árvores
- Árvore Binária: Cada nó tem no máximo 2 filhos (esquerdo/direito)
- Árvore Binária de Busca (ABB): Filhos à esquerda ≤ pai ≤ filhos à direita
- Árvore AVL: ABB com balanceamento (altura das subárvores difere no máximo em 1)
- Árvore B/B+: Usadas em bancos de dados (múltiplos filhos por nó)
3. Percursos (Traversal)
- Pré-ordem: Raiz → Esquerda → Direita
- Em-ordem (simétrico): Esquerda → Raiz → Direita (retorna valores ordenados em ABB)
- Pós-ordem: Esquerda → Direita → Raiz
- Em nível (BFS): Por camadas (usa fila)
4. Complexidade (Notação Big-O)
- ABB balanceada: Busca/Inserção/Remoção em O(log n)
- ABB degenerada (lista encadeada): Operações em O(n)
- AVL: Garante O(log n) com rotações para balanceamento
5. Aplicações em Concursos
- Questões sobre percurso e reconstrução de árvores
- Cálculo de altura/quantidade de nós
- Comparação entre estruturas (ABB vs. AVL vs. Hash)
- Implementação de algoritmos recursivos