Módulo 1 — Hash e Heap
Unidade 1 · Tabelas de Dispersão (Hash)
Uma tabela hash transforma uma chave em um índice de vetor usando uma função de dispersão. O objetivo é buscar, inserir e remover elementos em tempo médio O(1), sem percorrer toda a estrutura.
A função mais comum é h(k) = k mod m, onde k é a chave e m é o tamanho da tabela. O resultado é sempre um número entre 0 e m−1.
Exemplo
h(23) com m=7 → 7×3=21, 23−21=2 → posição
2Exemplo
h(58) com m=11 → 11×5=55, 58−55=3 → posição
3Exemplo
Dicionário Python (dict) é internamente uma tabela hash: {nome: Ana, idade: 20}. Acesso direto por chave em O(1).
⚠ Importante
Colisão ocorre quando duas chaves diferentes geram o mesmo índice. Ex: h(7)=0 e h(14)=0 com m=7 — ambas vão para posição 0.
⚠ Importante
Encadeamento: cada posição vira uma lista ligada. Elementos que colidem ficam na mesma posição: [7→14→21].
⚠ Importante
Sondagem linear: quando há colisão, procura a próxima posição livre. Fórmula: h(k,i) = (h(k)+i) mod m, onde i=0,1,2…
⚠ Importante
Fator de carga λ = n/m. Ideal manter λ < 0,75 para evitar muitas colisões.
⚠ Importante
Se a tabela encher com sondagem linear, o algoritmo entra em
loop infinito. Por isso λ < 0,75 é crítico!
Exercícios Resolvidos — Hash
Exercício 1: Com h(k)=k mod 11, em qual posição a chave k=58 é armazenada?
→ Posição 3
11×5=55. 58−55=3. Portanto h(58)=3.
Exercício 2: Tabela tam 7, posições 0 e 1 ocupadas. Inserindo k=14 com sondagem linear. Onde vai?
→ Posição 2
h(14)=0 (ocup) → i=1: pos 1 (ocup) → i=2: pos 2 (livre!).
Exercício 3: m=5, posições 0,1,2,4 ocupadas. Inserindo k=10 com sondagem linear. Onde vai?
→ Posição 3
h(10)=0 (ocup) → 1 (ocup) → 2 (ocup) → 3 (livre!).
Exercício 4: Com m=7, as chaves 7, 14 e 21 colidem. Como o encadeamento resolve?
→ Todas vão para posição 0. Lista [7→14→21].
7 mod 7=0, 14 mod 7=0, 21 mod 7=0. Todos múltiplos de 7 têm resto 0.
Módulo 1 — Hash e Heap
Unidade 2 · Lista de Prioridades (Heap)
Um heap é uma árvore binária quase completa (todos os níveis cheios exceto o último, preenchido da esquerda para a direita). É armazenado como vetor — não precisa de ponteiros.
Max-Heap
Todo pai é maior ou igual aos filhos. O maior elemento sempre fica na raiz — disponível em O(1).
Min-Heap
Todo pai é menor ou igual aos filhos. O menor elemento sempre fica na raiz — disponível em O(1).
Índices no array (começa em 1): Pai = ⌊i/2⌋ | Filho esq = 2×i | Filho dir = 2×i+1
Exemplo
Max-heap [90,75,60,40,55,30,25]: índice 3 (valor 60) → pai=índice 1 (90), filho esq=índice 6 (30), filho dir=índice 7 (25).
Exemplo
Inserindo 80 no max-heap: coloca no índice 8. Pai=índice 4 (40). 80>40, troca. Pai=índice 2 (75). 80>75, troca. Pai=índice 1 (90). 80<90, para. 80 fica no índice 2.
Exemplo
Fila de prioridade em hospitais: o paciente mais grave (maior prioridade) sempre sai primeiro — está sempre na raiz do max-heap.
⚠ Importante
Após inserir ou remover, é preciso restaurar com
heapify (sobe ou desce o elemento). Custo:
O(log n).
⚠ Importante
Heap
NÃO é uma árvore binária de busca. A propriedade esquerda < raiz < direita
não vale aqui.
⚠ Importante
Heap é a estrutura ideal para fila de prioridade: acesso ao maior/menor em
O(1) e inserção/remoção em
O(log n).
Exercícios Resolvidos — Heap
Exercício 5: No max-heap [90,75,60,40,55,30,25], qual é o pai e os filhos do índice 3 (valor 60)?
→ Pai=índice 1 (valor 90). Filho esq=índice 6 (valor 30). Filho dir=índice 7 (valor 25).
Pai = ⌊3/2⌋ = 1. Filho esq = 2×3 = 6. Filho dir = 2×3+1 = 7.
Exercício 6: V ou F — no max-heap, o menor elemento está sempre na raiz.
→ Falso
No MAX-heap o MAIOR elemento está na raiz. O menor está em alguma folha.
Exercício 7: Por que heap é melhor que array simples para fila de prioridade?
→ Heap: acesso ao maior em O(1), inserção/remoção em O(log n). Array: O(n) para achar o maior.
No array simples é preciso varrer todos os elementos. No max-heap, o maior está SEMPRE na raiz.
Módulo 2 — Árvore Binária de Busca (BST)
Unidade 1 · Inserção e Busca
Regra fundamental: todos os valores à ESQUERDA de um nó são MENORES que ele. Todos à DIREITA são MAIORES.
Busca: começa na raiz. Se o valor é menor → esquerda. Se maior → direita. Repete até encontrar ou posição vazia.
Inserção: segue o mesmo caminho da busca até posição vazia. Insere como folha.
Complexidade: O(h). Árvore balanceada: O(log n). Árvore degenerada: O(n).
Exemplo — Inserindo 5,3,8,1,4
raiz=5. 3<5 → esq. 8>5 → dir. 1<5<3 → esq de 3. 4>3<5 → dir de 3.
Exemplo — Buscando 4
Compara com 5 (4<5, esq) → compara com 3 (4>3, dir) → compara com 4 (encontrado!). Apenas 3 comparações.
Exemplo — Inserindo 45 na BST raiz=50
45<50 → esq. 45>30 → dir. 45>40 → dir de 40. O 45 vira filho direito do 40.
⚠ Importante
Se inserir elementos já ordenados (1,2,3,4,5…) a árvore vira uma lista ligada →
O(n) — caso degenerado!
⚠ Importante
O caso degenerado é o maior problema da BST simples. A
AVL resolve isso com balanceamento automático.
Exercícios Resolvidos — Inserção e Busca
Exercício 8: Na BST raiz=50 (filhos 30,70; netos 20,40,60,80), onde é inserido o valor 45?
→ Filho direito do nó 40.
45<50 → esq. 45>30 → dir. 45>40 → dir do 40.
Exercício 9: Na mesma BST, quantas comparações para buscar o valor 20?
→ 3 comparações.
Compara com 50 (esq) → compara com 30 (esq) → compara com 20 (encontrado!).
Módulo 2 — Árvore Binária de Busca (BST)
Unidade 2 · Percurso e Remoção
Pré-ordem
raiz → esq → dir
Útil para copiar ou serializar a árvore.
Em-ordem
esq → raiz → dir
Sempre resulta em ordem crescente em BST!
Pós-ordem
esq → dir → raiz
Útil para deletar a árvore (filhos antes do pai).
Remoção — 3 casos
Caso 1: folha → remove direto.
Caso 2: 1 filho → pai aponta pro filho.
Caso 3: 2 filhos → substitui pelo sucessor em-ordem.
Exemplo — Em-ordem raiz=50
Resultado:
20, 30, 40, 50, 60, 70, 80 — sempre ordem crescente!
Exemplo — Pré-ordem raiz=50
Resultado:
50, 30, 20, 40, 70, 60, 80 — raiz primeiro.
Exemplo — Removendo 30 (filhos 20 e 40)
Caso 3: dois filhos. Sucessor em-ordem = menor da subárvore direita = 40. O 40 sobe. O 20 fica como filho esq do 40.
Exemplo — Removendo 70 (filho dir=80)
Caso 2: um filho. O 80 sobe e ocupa o lugar do 70.
⚠ Importante
Sucessor em-ordem = menor elemento da subárvore
direita do nó removido.
⚠ Importante
O percurso
em-ordem em BST SEMPRE gera a sequência em ordem crescente. Propriedade fundamental!
Exercícios Resolvidos — Percurso e Remoção
Exercício 10: Resultado do percurso em-ordem na BST raiz=50 (filhos 30,70; netos 20,40,60,80)?
→ 20, 30, 40, 50, 60, 70, 80
Em-ordem (esq→raiz→dir) em BST SEMPRE resulta em ordem crescente.
Exercício 11: Resultado do percurso pré-ordem na mesma BST?
→ 50, 30, 20, 40, 70, 60, 80
Pré-ordem (raiz→esq→dir): começa pela raiz 50, percorre subárvore esq, depois dir.
Exercício 12: Removendo o nó 30 (filhos 20 e 40). Quem ocupa o lugar?
→ O nó 40 ocupa o lugar do 30. O 20 fica como filho esquerdo do 40.
Caso 3 — dois filhos. Sucessor em-ordem = menor da subárvore direita = 40.
Módulo 3 — Árvores Balanceadas (AVL)
Unidade 1 · Conceitos e Rotações
A AVL é uma BST que se auto-balanceia após cada inserção ou remoção. Resolve o problema da BST degenerada.
Fator de Balanceamento (FB) = altura(esq) − altura(dir). Folha = 0. Nó vazio = −1.
A AVL mantém FB ∈ {−1, 0, +1} em todos os nós. FB = ±2 → desbalanceado → rotação!
Como identificar a rotação:
Pergunta 1: FB do nó desbalanceado é +2 (desequilíbrio à esquerda) ou −2 (à direita)?
Pergunta 2: FB do filho tem o mesmo sinal → 1 rotação (caminho reto). Sinal oposto → 2 rotações (zigue-zague).
| Caso | FB do nó | FB do filho | Tipo | Rotação | Qtd |
|---|
| LL | +2 | +1 | Reto (esq-esq) | Simples à direita | 1 |
| RR | −2 | −1 | Reto (dir-dir) | Simples à esquerda | 1 |
| LR | +2 | −1 | Zigue-zague | Esq no filho + Dir na raiz | 2 |
| RL | −2 | +1 | Zigue-zague | Dir no filho + Esq na raiz | 2 |
Exemplo — LL: inserindo 30,20,10
Nó 30: FB=+2. Filho 20: FB=+1. Mesmo sinal → LL → 1 rotação à direita. O 20 vira raiz: [10 ← 20 → 30].
Exemplo — RR: inserindo 10,20,30
Nó 10: FB=−2. Filho 20: FB=−1. Mesmo sinal → RR → 1 rotação à esquerda. O 20 vira raiz: [10 ← 20 → 30].
Exemplo — LR: inserindo 30,10,20
Nó 30: FB=+2. Filho 10: FB=−1. Sinais opostos → LR → 2 rotações. O 20 vira raiz: [10 ← 20 → 30].
Exemplo — RL: inserindo 10,30,20
Nó 10: FB=−2. Filho 30: FB=+1. Sinais opostos → RL → 2 rotações. O 20 vira raiz: [10 ← 20 → 30].
⚠ Importante
O nó do
MEIO sempre vira a nova raiz em qualquer rotação AVL (LL, RR, LR, RL)!
⚠ Importante
LR e RL precisam de 2 rotações (zigue-zague). LL e RR precisam de apenas 1 rotação (caminho reto).
Exercícios Resolvidos — Rotações
Exercício 13: Inserindo 50,30,10. Nó 50 tem FB=+2, filho 30 com FB=+1. Qual caso, quantas rotações e quem vira raiz?
→ Caso LL — 1 rotação à direita — o 30 vira raiz: [10 ← 30 → 50].
FB=+2 → esquerda. Filho esq (30) FB=+1 → mesmo sinal → caminho reto → LL.
Exercício 14: Inserindo 10,30,20. Nó 10 tem FB=−2, filho 30 com FB=+1. Qual caso e resultado?
→ Caso RL — 2 rotações — o 20 vira raiz: [10 ← 20 → 30].
FB=−2 → direita. Filho dir (30) FB=+1 → sinal oposto → zigue-zague → RL.
Exercício 15: Inserindo 30,10,20. Nó 30 tem FB=+2, filho 10 com FB=−1. Qual caso e resultado?
→ Caso LR — 2 rotações — o 20 vira raiz: [10 ← 20 → 30].
FB=+2 → esquerda. Filho esq (10) FB=−1 → sinal oposto → zigue-zague → LR.
Módulo 3 — Árvores Balanceadas (AVL)
Unidade 2 · Inserção e Remoção na AVL
Inserção na AVL: insere igual à BST normal. Depois sobe pelo caminho verificando o FB de cada nó. Se algum tiver FB=±2, aplica a rotação adequada.
Remoção na AVL: remove igual à BST normal (3 casos). Depois sobe verificando FB e aplicando rotações. Pode precisar de rotações em mais de um nó.
Exemplo — inserindo 10,20,30
Após inserir 30: FB da raiz 10 = −2, filho 20 FB=−1 → RR → rotação esquerda → 20 vira raiz, 10 esq, 30 dir.
Exemplo — inserindo 10,20,30,40,50
Após inserir 40: nó 20 FB=−2, filho 30 FB=−1 → RR → rotação. Após inserir 50: nó 30 FB=−2 → nova rotação. AVL rebalanceia a cada inserção.
⚠ Importante
AVL garante
SEMPRE O(log n) para busca, inserção e remoção — ao contrário da BST simples, nunca degenera em lista.
⚠ Importante
O custo extra das rotações é O(log n) no pior caso — vale a pena para garantir buscas rápidas em qualquer situação.
⚠ Importante
A altura de uma AVL com n nós é sempre
O(log n). Isso garante que todas as operações sejam eficientes.
Exercícios Resolvidos
Exercício 16: Um nó tem subárvore esq altura 2 e subárvore dir altura 0. FB=? Está balanceado?
→ FB = 2−0 = +2, DESBALANCEADO. Filho esq FB=+1 → LL (1 rotação). Filho esq FB=−1 → LR (2 rotações).
FB = altura(esq)−altura(dir) = 2−0 = +2. Como |FB| > 1, está desbalanceado.
Exercício 17: V ou F — após cada inserção em AVL, todos os nós precisam ser rotacionados.
→ Falso
Apenas os nós com FB=±2 são rotacionados. Na maioria dos casos, apenas 1 ou 2 rotações bastam para rebalancear.
Módulo 4 — Desafios de Programação
Unidade 1 · Aplicações com Hash
Tabela hash é ideal quando precisamos de acesso rápido por uma chave e a ordem dos elementos não importa.
Hash criptográfico é diferente do hash de tabela: foi projetado para ser irreversível e resistente a colisões intencionais.
Exemplo
Contar frequência de palavras: cada palavra é a chave, a contagem é o valor. Atualização em O(1).
Exemplo
Verificar duplicatas: inserir cada elemento no hash. Se já existe → é duplicata. O(n) total, vs O(n²) da força bruta.
Exemplo
Hash criptográfico SHA-256: "senha123" → sempre o mesmo hash. Dado o hash,
impossível descobrir "senha123". Usado em bancos de dados de senhas.
⚠ Importante
Hash criptográfico é
IRREVERSÍVEL — dado o hash, não dá para descobrir o valor original. Por isso é usado para proteger senhas.
⚠ Importante
Escolha hash quando: busca por chave em O(1), não precisa de ordem, chave única por elemento.
Unidade 2 · Aplicações com Árvores
Código de Huffman: compressão sem perda. Símbolos mais frequentes ficam mais perto da raiz e recebem códigos menores.
Exemplo — Huffman: "aabbbcccc"
Frequências: a=2, b=3, c=4. Na árvore: c → código menor (ex: 0), b → médio (ex: 10), a → maior (ex: 11). Letras frequentes usam menos bits.
Exemplo — Dijkstra
Usa min-heap: sempre processa o vértice com menor distância acumulada. Heap garante O(log n) por operação.
⚠ Importante
Huffman: compressão ótima quando a frequência dos símbolos é conhecida. Muito usado em JPEG, MP3 e ZIP.
⚠ Importante
Use
BST/AVL para buscar qualquer elemento. Use
Heap para maior/menor. Use
Hash para buscar por chave específica.
Exercícios Resolvidos — Aplicações
Exercício 18: Por que sistemas guardam o HASH da senha e não a senha em texto puro?
→ Hash criptográfico é irreversível — protege usuários mesmo se o banco de dados vazar.
O sistema calcula h(senha) no login e compara com o hash armazenado. Quem rouba o banco só vê hashes — não consegue reverter para descobrir as senhas originais.
Exercício 19: No código de Huffman, a letra que aparece 100 vezes terá código binário maior ou menor que a que aparece 2 vezes?
→ Menor — letras mais frequentes têm códigos MENORES (menos bits).
Huffman coloca símbolos mais frequentes mais perto da raiz. Quanto mais perto da raiz, menor o caminho e menor o código binário gerado.
Exercício 20: Por que o heap é melhor que a BST simples para fila de prioridade?
→ Heap garante O(log n) sempre. BST simples pode degenerar para O(n) com inserções ordenadas.
No heap a estrutura NUNCA degenera — sempre árvore quase completa com altura O(log n). Na BST simples, inserir em ordem cria lista ligada.
🗒 Cola de Prova — Resumo Geral
Comparativo de Estruturas
| Estrutura | Para que serve | Complexidade principal |
|---|
| Hash | Busca rápida por chave específica | O(1) médio, O(n) pior caso |
| Heap | Achar maior/menor sempre disponível | O(1) raiz, O(log n) ins/rem |
| BST | Busca ordenada e dinâmica | O(h): O(log n) bal., O(n) deg. |
| AVL | BST sempre balanceada | O(log n) garantido sempre |
Tabela de Rotações AVL
| Caso | FB nó | FB filho | Tipo | Rotações |
|---|
| LL → direita | +2 | +1 | Reto | 1 |
| RR → esquerda | −2 | −1 | Reto | 1 |
| LR → esq+dir | +2 | −1 | Zigue-zague | 2 |
| RL → dir+esq | −2 | +1 | Zigue-zague | 2 |
Percursos BST
| Percurso | Ordem de visita | Resultado (raiz=50) |
|---|
| Em-ordem | esq → raiz → dir | 20,30,40,50,60,70,80 (SEMPRE crescente!) |
| Pré-ordem | raiz → esq → dir | 50,30,20,40,70,60,80 |
| Pós-ordem | esq → dir → raiz | 20,40,30,60,80,70,50 |
Remoção BST — 3 Casos
| Caso | Quando ocorre | Como resolver |
|---|
| Caso 1: folha | Nó sem filhos | Remove direto, sem reorganizar |
| Caso 2: 1 filho | Nó com apenas um filho | Conecta o pai diretamente ao filho do removido |
| Caso 3: 2 filhos | Nó com filho esq e dir | Substitui pelo sucessor em-ordem (menor da subárvore dir) |
⭐ Regras de Ouro para a Prova
Regra
O nó do
MEIO sempre vira a nova raiz nas rotações AVL (LL, RR, LR e RL)
Regra
Em-ordem em BST =
SEMPRE ordem crescente (propriedade fundamental)
Regra
λ = n/m ideal
< 0,75 para tabela hash (evita colisões excessivas)
Regra
Heap: pai ≥ filhos (max-heap) | pai ≤ filhos (min-heap)
Regra
Hash criptográfico é
IRREVERSÍVEL — hash de tabela não necessariamente
Regra
BST pode degenerar em lista O(n) —
AVL resolve com rotações automáticas
Regra
Mesmo sinal nos FBs = 1 rotação (caminho reto).
Sinais opostos = 2 rotações (zigue-zague)