Programação das aulas

Sujeito a mudanças...

Março

Abril

• 3 de abril (Aula 9):
  • Árvores e árvores binárias de busca (ABBs)
  • Lista 4
  Transparências [pdf][ps.gz]
  Leitura recomendada: Cap 12 do CLRS.

• 13 de abril (Aula 10):
  • Árvores rubro-negras

• 17 de abril (Aula 11):
  • Árvores 2-3 e 2-3-4 e sua relação com ABBs rubro-negras
  • Inserção em árvores rubro-negras
  Transparências [pdf][ps.gz]
  Leitura recomendada: Cap 13 do CLRS, artigo do Sedgewick [pdf] e transparências do Sedgewick, acessíveis aqui. Cuidado que há alguns erros em alguns destes códigos.

  Mencionei splay trees na aula, como exemplo de outro tipo de árvore com algum balanceamento. Se você quiser saber um pouco sobre elas, visite a página wiki delas, ou veja a seção 13.2 do livro "Algorithms in C", do Sedgewick, ou a Lecture 12 do livro "The Design and Analysis of Algorithms", de Kozen.

• 24 de abril (Aula 12):
  • Correção da inserção em árvores 2-3 e 2-3-4
  • Remoção em ABBs
  • Remoção de mínimo em árvores 2-3
  Transparências [pdf][ps.gz]
  Leitura recomendada: Seções 13.3 e 13.4 do livro do Sedgewick. Na 13.3, ele fala de árvores 2-3-4, e na seguinte de rubro-negras. Há neste cap 13 um estudo experimental envolvendo ABBs, splay trees, rubro-negras, e skip lists. Vale a pena dar uma olhada.

• 28 de abril (Aula 13):
  • Remoção em árvores rubro-negras
  • Árvores AVL
  Transparências [pdf][ps.gz]
  Leitura recomendada: Sec 4.5 do livro Algorithms and Data Structures, de Wirth.

Maio