Resumo Estruturas de Dados II

Prévia do material em texto

Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 1
ESTRUTURAS DE DADOS II
Material de Estudo Completo
Resumos Detalhados • Pseudocódigos • Exercícios Resolvidos
Este material consolida as 8 aulas da disciplina, com explicações claras, algoritmos em pseudocódigo prontos
para estudo e exercícios com soluções para treino e fixação do conteúdo.
Conteúdo
coberto:
Listas • Tabelas Hash • Árvores • ABB • AVL • Árvores B • Compactação
Objetivo: Material imprimível para revisão e prática autônoma
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 2
ÍNDICE
1. Relembrando Listas (Listas Lineares, Encadeadas, Pilhas e Filas)
2. Tabelas Hash (Funções de Dispersão e Tratamento de Colisões)
3. Introdução às Árvores e Árvores Binárias
4. Árvores de Busca Binária – Parte I (Percursos e Busca)
5. Árvores de Busca Binária – Parte II (Inserção e Remoção)
6. Árvores AVL (Balanceamento e Rotações)
7. Árvores B (Definição, Busca e Inserção)
8. Compactação de Arquivos (Run-Length e Huffman)
Apêndice: Dicas de Estudo e Checklist Final
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 3
AULA 1 — RELEMBRANDO LISTAS
Objetivos de aprendizagem
• Relembrar o conceito de listas e suas propriedades estruturais.
• Diferenciar listas lineares (por contiguidade) de listas encadeadas.
• Compreender as disciplinas de acesso: pilhas (LIFO) e filas (FIFO).
• Dominar as operações básicas de busca, inserção e remoção.
1.1 Conceito de Lista
Uma lista é um conjunto de n ≥ 0 nós dispostos de forma linear, em que as propriedades estruturais decorrem
unicamente da posição relativa dos nós. Se n = 0 a lista está vazia. Usualmente os elementos são registros
identificados por um campo-chave (ex.: RGM de aluno).
1.2 Listas com Disciplina de Acesso
Pilha (LIFO – Last In, First Out)
O último elemento inserido é o primeiro a ser removido. Operações: EMPILHAR (insere no topo) e
DESEMPILHAR (remove do topo).
Fila (FIFO – First In, First Out)
O primeiro elemento a entrar é o primeiro a sair. Operações: ENFILEIRAR (insere no fim) e DESENFILEIRAR
(remove do início).
1.3 Lista Linear (por contiguidade)
Implementada sobre um vetor de tamanho fixo M. Variáveis de controle: tamanho (capacidade) e preenchidos
(quantidade atual). Vantagem: simplicidade. Desvantagens: limite pré-definido e possível movimentação de
elementos na inserção/remoção.
Pseudocódigo – Busca Linear
funcao BUSCA(x : inteiro) : inteiro
 var i : inteiro
inicio
 i 0) entao
 indice -1) entao
 para i de indice ate preenchidos-1 faca
 lista[i] proxnão possui pai.
Filho / Pai: Descendentes diretos de um nó / nó superior imediato.
Grau de um nó: Número de filhos (subárvores) que o nó possui.
Folha: Nó de grau zero (sem filhos).
Altura / Profundidade: Número de níveis entre a raiz e a folha mais profunda (há divergência se a contagem
começa em 0 ou 1).
Floresta: Conjunto de duas ou mais árvores desconectadas.
Nível: Raiz no nível 1 (ou 0); filhos da raiz no nível seguinte, e assim por diante.
3.4 Árvores Binárias
Árvore em que todo nó tem grau ≤ 2 (no máximo dois filhos: esquerdo e direito). Implementação típica com
registro contendo o dado e dois ponteiros:
tipo registro TArvore:
 dado : inteiro
 esq : *TArvore
 dir : *TArvore
fimregistro
Exercícios – Aula 3
Exercício 3.1
Em uma árvore com raiz A, filhos B e C; B sem filhos; C com filhos D, E e F; D com filhos G e H. Identifique: (a)
folhas; (b) grau de C; (c) altura da árvore (contando raiz como nível 1).
Solução:
(a) Folhas: B, E, F, G, H
(b) Grau de C = 3
(c) Altura = 4 (níveis: A=1, C=2, D=3, G/H=4)
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 7
AULA 4 — ÁRVORES DE BUSCA BINÁRIA – PARTE I
4.1 Definição e Propriedade Fundamental
Uma Árvore de Busca Binária (ABB) é uma árvore binária em que, para todo nó:
• Todos os valores na subárvore esquerda são menores que o valor do nó;
• Todos os valores na subárvore direita são maiores que o valor do nó.
Essa propriedade permite busca eficiente: a cada passo descartamos metade dos candidatos (semelhante à
busca binária, porém sobre estrutura dinâmica).
4.2 Percursos
Pré-ordem: visita o nó → percorre esquerda → percorre direita.
Pós-ordem: percorre esquerda → percorre direita → visita o nó.
In-ordem: percorre esquerda → visita o nó → percorre direita. Resultado: elementos em ordem crescente.
Pseudocódigo – In-ordem
procedimento inOrdem(Raiz: *TArvore)
inicio
 se (Raiz ≠ NULO) entao
 inOrdem(Raiz->esq)
 VisitaNo(Raiz) // escreve Raiz->dado
 inOrdem(Raiz->dir)
 fimse
fimprocedimento
4.3 Busca em ABB
funcao buscaABB(Raiz: *TArvore, chave: inteiro) : *TArvore
inicio
 se (Raiz ≠ NULO) entao
 enquanto (Raiz->dado ≠ chave) e (Raiz ≠ NULO) faca
 se (chave dado) entao
 Raiz esq
 senao
 Raiz dir
 fimse
 fimenquanto
 fimse
 retorne Raiz // NULO se não encontrou
fimfuncao
Mínimo e Máximo
procedimento minimo(Raiz: *TArvore)
inicio
 enquanto (Raiz->esq ≠ NULO) faca
 Raiz esq
 fimenquanto
 retorne Raiz
fimprocedimento
procedimento maximo(Raiz: *TArvore)
inicio
 enquanto (Raiz->dir ≠ NULO) faca
 Raiz dir
 fimenquanto
 retorne Raiz
fimprocedimento
Exercícios – Aula 4
Exercício 4.1
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 8
Considere a ABB com os valores inseridos na ordem: 30, 13, 45, 10, 17, 40, 70, 21. Qual a sequência gerada por
um percurso in-ordem? E pré-ordem?
Solução:
In-ordem (crescente): 10, 13, 17, 21, 30, 40, 45, 70
Pré-ordem: 30, 13, 10, 17, 21, 45, 40, 70
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 9
AULA 5 — ÁRVORES DE BUSCA BINÁRIA – PARTE II
5.1 Inserção
1. Aloca o novo nó (dado = chave, esq = dir = NULO).
2. Procura o pai percorrendo a árvore (mesma lógica da busca) até encontrar ponteiro NULO.
3. Se a árvore estava vazia, o novo nó vira a raiz. Caso contrário, liga o novo nó à esquerda ou à direita do pai
conforme a comparação.
procedimento insere(chave: inteiro, Raiz: *TArvore)
 declare NovoNo, Pai, Atual: *TArvore
inicio
 NovoNo dado esq dir dado) entao
 Atual esq
 senao
 Atual dir
 fimse
 fimenquanto
 se (Pai = NULO) entao
 Arvore.raiz dado) entao
 Pai->esq dir esq) entao
 pai_u->esq dir esq = NULO) entao
 transplantar(NoRemover, NoRemover->dir) // 0 ou só direito
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 10
 senao se (NoRemover->dir = NULO) entao
 transplantar(NoRemover, NoRemover->esq) // só esquerdo
 senao
 Sucessor dir)
 se (pai(Sucessor) ≠ NoRemover) entao
 transplantar(Sucessor, Sucessor->dir)
 Sucessor->dir dir
 fimse
 transplantar(NoRemover, Sucessor)
 Sucessor->esq esq
 fimse
fimprocedimento
Exercícios – Aula 5
Exercício 5.1
Na ABB do exercício 4.1 (raiz 30), mostre a árvore após a inserção do valor 20 e após a remoção do valor 13.
Solução (textual):
Inserção de 20: 20 é maior que 13 e menor que 21 → fica à esquerda de 21.
Remoção de 13 (tem dois filhos: 10 e 17): sucessor = mínimo da direita = 17. 17 sobe para o lugar de 13; o filho
direito original de 17 (21) passa a ser filho direito do novo 17. O filho esquerdo de 13 (10) torna-se filho esquerdo
de 17.
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 11
AULA 6 — ÁRVORES AVL
6.1 Motivação e Definição
Em ABBs comuns a sequência de inserção pode gerar árvores degeneradas (quase listas), prejudicando a busca.
A árvore AVL (Adelson-Velsky e Landis, 1962) mantém o balanceamento local: para todo nó, a diferença de altura
entre as subárvores esquerda e direita é no máximo 1.
6.2 Fator de Balanceamento (FB)
FB(Nó) = HE − HD, onde HE = altura da subárvore esquerda e HD = altura da direita.
Valores permitidos: −1, 0, +1. Se após inserção/remoção algum nó ficar com |FB| = 2, é necessário rebalancear
por meio de rotações.
6.3 As Quatro Rotações
Rotação simples à esquerda: usada quando o desbalanceamento é “para a direita” (FB = −2) e o filho direito
tem FB ≤ 0.
Rotação simples à direita: simétrica (FB = +2 e filho esquerdo com FB ≥ 0).
Rotação dupla esquerda (direita-esquerda): primeiro rotação à direita no filho direito, depois rotação à
esquerda no nó desbalanceado.
Rotação dupla direita (esquerda-direita): primeiro rotação à esquerda no filho esquerdo, depois rotação à
direita no nó desbalanceado.
Resumo de decisão (após inserção do nó q, nó desbalanceado mais próximo = p):
• HE(p) > HD(p) e HE(u) ≥ HD(u) → rotação simples à direita em p
• HE(p) > HD(p) e HD(u) > HE(u) → rotação dupla direita
• HD(p) > HE(p) e HD(z) ≥ HE(z) → rotação simples à esquerda em p
• HD(p) > HE(p) e HE(z) > HD(z) → rotação dupla esquerda
Exercícios – Aula 6
Exercício 6.1
Insira os valores 10, 20, 30 em uma AVL inicialmente vazia. Descreva as rotações necessárias.
Solução:
Após 10 e 20: árvore 10→20 (direita). FB(10) = −1 (ok).
Inserção de 30: 10→20→30. FB(10) = −2. Filho direito (20) tem FB = −1 → rotação simples à esquerda em 10.
Resultado: raiz 20, esquerda 10, direita 30 (perfeitamente balanceada).
Estruturas de Dados II — Material de Estudo Completo Resumo + Exercícios
Página 12
AULA 7 — ÁRVORES B
7.1 Motivação
Discos rígidos (e mesmo SSDs) são ordens de magnitude mais lentos quea memória RAM. Árvores B minimizam
o número de acessos a disco armazenando múltiplas chaves por nó e mantendo a árvore rasa (baixa altura).
7.2 Propriedades Formais (grau mínimo t)
• Todo nó (exceto raiz) tem pelo menos t−1 chaves e no máximo 2t−1 chaves.
• Todo nó interno com n chaves possui n+1 filhos.
• Todas as folhas estão no mesmo nível (árvore perfeitamente balanceada em altura).
• As chaves dentro de um nó estão ordenadas e separam os intervalos das subárvores.
Exemplo clássico: árvore 2-3-4 (t = 2) → cada nó tem 1 a 3 chaves e 2 a 4 filhos.
7.3 Busca
funcao busca(x: *TArvore, k: inteiro) : (nó, índice)
inicio
 i x.chave[i]) faca
 i