Sujeito a mudanças...
- 4 de abril (Aula 10):
- Árvores e árvores binária
- Algoritmos em árvores (percursos pré, in e pós-ordem, etc)
Exercício 1: Escreva uma função que conta o
número de folhas de uma árvore binária. Reescreva uma função para
contar o número de folhas de uma árvore arbitrária (dada pela
representação primeirofilho/irmão).
Exercício 2: Escreva uma função que calcula
a altura de uma árvore binária. Reescreva uma função para calcular
a altura de uma árvore arbitrária (dada pela representação
primeirofilho/irmão).
Leitura recomendada: CLRS, sec 10.4.
- 6 de abril (Aula 11):
- Árvore binária de busca (ABB): definição, busca, máximo,
sucessor, inserção
- Lista 3 (árvores, árvores binárias e ABBs)
[ps.gz] [pdf]
Leitura recomendada: CLRS, secs 12.1-12.3.
- 11 e 13 de abril:
- Semana Santa (segunda semana de break)
- 18 de abril (Aula 12):
- ABBs: remoção
- Árvores com fios
Exercícios: Reescreva as funções
minimo, sucessor, busca, insere para uma ABB com fios.
Leitura recomendada: sec 3.6 do livro do
Jayme Szwarcfiter e Lilian Markenzon, Estruturas de Dados e seus
Algoritmos.
- 20 de abril (Aula 13):
- Colocação de fios em uma ABB.
- Altura de árvores de busca binária aleatórias (CLRS sec 12.4)
- Lista 4 (mais uns de árvores; veja abaixo a nova versão)
- 25 de abril (Aula 14):
- Altura de árvores de busca binária aleatórias: finalização
da análise
- Árvores rubro-negras: definição e análise da altura (CLRS cap 13)
- 27 de abril (Aula 15):
- Árvores rubro-negras: inserção
- Lista 4 - nova versão (com questões sobre árvores rubro-negras)
[ps.gz] [pdf]